在java中,下面哪个数据结构是支持排序的,数据结构各种排序

　　00-1010I、插入排序1、直接插入排序2、希尔排序2、选择排序1、选择排序2、堆排序3、交换排序1、冒泡排序2、快速排序4、归并排序5、排序算法分析

　　00-1010 Hill排序法的基本思想是：首先选择一个整数gap，将待排序文件中的所有记录划分为gap组，所有距离为gap的数字都划分为同一组，直接对每组中的数字进行插入排序。然后取gap=gap/2，重复上述分组排序。当gap=1时，所有数字通过在组内直接插入来排序。

　　希尔排序是直接插入排序的优化。当使用间隙1时，它是预先排序的，以便使数组更接近有序。当gap==1时，数组几乎是有序的，直接插入排序会很快。Hill排序的时间复杂度不好计算，因为gap的方法很多，计算起来比较困难。希尔排序：

　　public static void shell sort(int[]array){ int size=array . length；//这里定义的gap的初始值是数组长度的一半int gap=size/2；While(gap0){ //直接插入排序for(int I=gap；I尺寸；I){ int tmp=array[I]；int j=I-gap；for(；j=0；j-=gap){ if(array[j]tmp){ array[j gap]=array[j]；} else { break} } array[j gap]=tmp；} gap/=2；} }

一、插入排序

　　00-1010选择元素集array [i]-array [n-1]中最小的数据元素。如果不是这个集合中的第一个元素，在剩余集合中与这个集合中的第一个元素交换，重复上述步骤，直到集合中还有一个剩余元素。时间复杂度：O(n ^ 2)

　　空间复杂度为O(1)，不稳定。

　　选择排序：

　　//Exchange私有静态void swap (int [] array，int i，int j){ int tmp=array[I]；array[I]=array[j]；array[j]=tmp；}//Select排序公共静态void chooseSo

　　rt(int[] array){ for (int i = 0; i < array.length; i++) { int minIndex=i;//记录最小值的下标 for (int j = i+1; j < array.length; j++) { if (array[j]<array[minIndex]) { minIndex=j; } } swap(array,i,minIndex); } }

2、堆排序

堆排序的两种思路（以升序为例）：

　　创建小根堆，依次取出堆顶元素放入数组中，直到堆为空创建大根堆，定义堆的尾元素位置key，每次交换堆顶元素和key位置的元素（key--），直到key到堆顶，此时将堆中元素层序遍历即为升序（如下）时间复杂度：O(N^2)

　　空间复杂度：O(N)，不稳定

　　堆排序：

 //向下调整 public static void shiftDown(int[] array,int parent,int len){ int child=parent*2+1; while(child<len){ if(child+1<len){ if(array[child+1]>array[child]){ child++; } } if(array[child]>array[parent]){ swap(array,child,parent); parent=child; child=parent*2+1; }else{ break; } } } //创建大根堆 private static void createHeap(int[] array){ for (int parent = (array.length-1-1)/2; parent >=0; parent--) { shiftDown(array,parent,array.length); } } //堆排序 public static void heapSort(int[] array){ //创建大根堆 createHeap(array); //排序 for (int i = array.length-1; i >0; i--) { swap(array,0,i); shiftDown(array,0,i); } }

三、交换排序

1、冒泡排序

两层循环，第一层循环表示要排序的趟数，第二层循环表示每趟要比较的次数；这里的冒泡排序做了优化，在每一趟比较时，我们可以定义一个计数器来记录数据交换的次数，如果没有交换，则表示数据已经有序，不需要再进行排序了。

　　时间复杂度：O(N^2)

　　空间复杂度为O(1),是一个稳定的排序

　　冒泡排序：

 public static void bubbleSort(int[] array){ for(int i=0;i<array.length-1;++i){ int count=0; for (int j = 0; j < array.length-1-i; j++) { if(array[j]>array[j+1]){ swap(array,j,j+1); count++; } } if(count==0){ break; } } }

2、快速排序

任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

　　时间复杂度：最好O(n*logn):每次可以尽量将待排序的序列均匀分割

　　最坏O(N^2)：待排序序列本身是有序的

　　空间复杂度：最好O(logn)、最坏O(N)。不稳定的排序

　　（1）挖坑法

　　当数据有序时，快速排序就相当于二叉树没有左子树或右子树，此时空间复杂度会达到O(N)，如果大量数据进行排序，可能会导致栈溢出。

public static void quickSort(int[] array,int left,int right){ if(left>=right){ return; } int l=left; int r=right; int tmp=array[l]; while(l<r){ while(array[r]>=tmp&&l<r){ //等号不能省略，如果省略，当序列中存在相同的值时，程序会死循环 r--; } array[l]=array[r]; while(array[l]<=tmp&&l<r){ l++; } array[r]=array[l]; } array[l]=tmp; quickSort(array,0,l-1); quickSort(array,l+1,right); }

（2）快速排序的优化

　　三数取中法选key

　　关于key值的选取，如果待排序序列是有序的，那么我们选取第一个或最后一个作为key可能导致分割的左边或右边为空，这时快速排序的空间复杂度会比较大，容易造成栈溢出。那么我们可以采用三数取中法来取消这种情况。找到序列的第一个，最后一个，以及中间的一个元素，以他们的中间值作为key值。

 //key值的优化，只在快速排序中使用，则可以为private private int threeMid(int[] array,int left,int right){ int mid=(left+right)/2; if(array[left]>array[right]){ if(array[mid]>array[left]){ return left; } return array[mid]<array[right]?right:mid; }else{ if(array[mid]<array[left]){ return left; } return array[mid]>array[right]?right:mid; } }

递归到小的子区间时，可以考虑用插入排序

　　随着我们递归的进行，区间会变的越来越小，我们可以在区间小到一个值的时候，对其进行插入排序，这样代码的效率会提高很多。

　　（3）快速排序的非递归实现

 //找到一次划分的下标 public static int patition(int[] array,int left,int right){ int tmp=array[left]; while(left<right){ while(left<right&&array[right]>=tmp){ right--; } array[left]=array[right]; while(left<right&&array[left]<=tmp){ left++; } array[right]=array[left]; } array[left]=tmp; return left; } //快速排序的非递归 public static void quickSort2(int[] array){ Stack<Integer> stack=new Stack<>(); int left=0; int right=array.length-1; stack.push(left); stack.push(right); while(!stack.isEmpty()){ int r=stack.pop(); int l=stack.pop(); int p=patition(array,l,r); if(p-1>l){ stack.push(l); stack.push(p-1); } if(p+1<r){ stack.push(p+1); stack.push(r); } } }

四、归并排序

归并排序（MERGE-SORT）：该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

　　时间复杂度：O(n*logN)（无论有序还是无序）

　　空间复杂度：O（N）。是稳定的排序。

 //归并排序：递归 public static void mergeSort(int[] array,int left,int right){ if(left>=right){ return; } int mid=(left+right)/2; //递归分割 mergeSort(array,left,mid); mergeSort(array,mid+1,right); //合并 merge(array,left,right，mid); } //非递归 public static void mergeSort1(int[] array){ int gap=1; while(gap<array.length){ for (int i = 0; i < array.length; i+=2*gap) { int left=i; int mid=left+gap-1; if(mid>=array.length){ mid=array.length-1; } int right=left+2*gap-1; if(right>=array.length){ right=array.length-1; } merge(array,left,right,mid); } gap=gap*2; } } //合并：合并两个有序数组 public static void merge(int[] array,int left,int right，int mid){ int[] tmp=new int[right-left+1]; int k=0; int s1=left; int e1=mid; int s2=mid+1; int e2=right; while(s1<=e1&&s2<=e2){ if(array[s1]<=array[s2]){ tmp[k++]=array[s1++]; }else{ tmp[k++]=array[s2++]; } } while(s1<=e1){ tmp[k++]=array[s1++]; } while(s2<=e2){ tmp[k++]=array[s2++]; } for (int i = left; i <= right; i++) { array[i]=tmp[i-left]; } }

五、排序算法的分析

排序方法最好时间复杂度最坏时间复杂度空间复杂度稳定性直接插入排序O(n)O(n^2)O(1)稳定希尔排序O(n)O(n^2)O(1）不稳定直接排序O(n^2)O(n^2)O(1)不稳定堆排序O(nlog(2)n)O(nlog(2)n)O(1)不稳定冒泡排序O(n)O(n^2)O(1)稳定快速排序O(nlog(2)n)O(n^2)O(nlog(2)n)不稳定归并排序O(nlog(2)n)O(nlog(2)n)O(n)稳定到此这篇关于Java 数据结构七大排序使用分析的文章就介绍到这了,更多相关Java 排序内容请搜索盛行IT以前的文章或继续浏览下面的相关文章希望大家以后多多支持盛行IT！

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。