大家好，欢迎来到IT知识分享网。
1.希尔排序
希尔排序是插入排序的改进，不必再像插入排序一样一个一个比较再交换，它的精髓在于增量交换，因此又叫做缩小增量排序。常用初始增量为len/2，这样就把所有元素分为了若干组，每次通过比较、交换相差增量的元素，然后缩小增量，重复这个过程直至增量变为1，这样每一个元素都排好了位置。希尔排序的时间复杂度为O(nlogn)，是首个时间复杂度冲破O(n^2)的算法。
下面是它的java代码实现
@Test public void sort(){ int []array = new int[100000]; Random random = new Random(); for (int i =0;i < 100000;i++){ array[i]= random.nextInt(9000000); } //实现 for (int d = array.length/2 ; d > 0 ; d/=2) {//初始增量d为len/2，每次缩小一半直至最后为1 for (int i = d ;i<array.length;i++){//循环每一个分组 for (int j = i-d;j>=0 && array[j+d]<array[j];j-=d){//同一组且相邻增量的元素比较大小并交换，此循环结束代表该组的大小排序完成 swap(array,j,j+d); } } } log.info(Arrays.toString(array)); } //交换元素 void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }
经过测试，10w个元素的数组使用希尔排序耗时436ms
2.插入排序
看不懂希尔排序的话，不如先看看插入排序，插入排序顾名思义，把最小或最大的元素插入到合适的位置直至遍历所有元素即可。也就是说插入排序要把第一个元素看作是有序的，从第二个元素开始和前一个元素比较
大小，若符所有元素即可。也就是说插入排序要把第一个元素看作是有序的，从第二个元素开始和前一个元素比较大小，若符合条件则交换他们，重复这个过程直到不符合条件为止，这样一来这个元素之前的都是有序的
，之后的都是无序的。重复这个过程直到最后一个元素比较完，排序就结束了。插入排序时间复杂度为O(n^2)
下面是代码实现
@Test public void sort(){ int []array = new int[100000]; Random random = new Random(); for (int i =0;i < 100000;i++){ array[i]= random.nextInt(9000000); } //实现 for (int i = 1;i<array.length;i++){ for (int j = i-1;j>=0;j--){ if (array[j+1]<array[j]){ swap(array,j,j+1); } } } log.info(Arrays.toString(array)); }
经过测试，10w个元素的数组使用插入排序耗时10s175ms
是不是相差挺大的，当数据量小的时候两个算法差异还差不多，数据量大起来，耗费的时间只会越拉越大。不过细心的小伙伴已经发现了，内层循环里面的逻辑仅仅只有一个交换逻辑，所以这个代码可以优化成下面的样子
//实现 for (int i = 1;i<array.length;i++){ for (int j = i-1; j>=0 && array[j+1]<array[j] ;j--){ swap(array,j,j+1); } } 优化后的代码耗时4s232ms
这样的话代码就是最优的了
3.归并排序
归并排序典型的运用了分治法、递归的思想，但是它需要用到额外的内存空间，简单来说需要不断的分割原数组至所有元素只剩一个，然后比较大小把值赋给中间数组，最后中间数组把值赋值给原数组。由于运用了
递归的思想，只需要每次将数组分割为两份，直至所有数组里的元素只剩一个，然后比较大小递归的合并他们。这样中间数组的值就已经全部有序，最后将中间数组复制给原数组，排序就结束了。说着很简单，让我
们来看看代码实现
@Test public void sort(){ int []array = new int[200000]; Random random = new Random(); for (int i =0;i < 200000;i++){ array[i]= random.nextInt(9000000); } //实现 int length = array.length; int []tmp = new int[length]; mergeSort(array,0,length-1,tmp); log.info(Arrays.toString(array)); } void mergeSort(int []array, int left ,int right, int []tmp){ int mid = (left+right)/2; if (left<right){//拆分至每组只有一个元素 mergeSort(array, left, mid, tmp); mergeSort(array, mid+1, right, tmp); merge(array, left, right, tmp); } } void merge(int []array, int left ,int right ,int []tmp){ int mid = (left+right)/2; int i = left; //左哨兵 int j = mid +1;//右哨兵 int index = 0;//中间数组下标 while (i<=mid && j<=right){//左右两个哨兵指向的值比较大小并存入中间数组，总有一个哨兵走到尽头，跳出循环 if (array[i]<=array[j]){ tmp[index++]=array[i++]; }else { tmp[index++]=array[j++]; } } while (j<=right){//左哨兵走到尽头，右哨兵剩余未走的值全部复制给中间数组 tmp[index++]=array[j++]; } while (i<=mid){//右哨兵走到尽头，左哨兵剩余未走的值全部复制给中间数组 tmp[index++]=array[i++]; } index = 0; while(left<=right){//把中间数组的值复制给原数组 array[left++] = tmp[index++]; }
}
经过测试，20w条数据，归并排序仅需要564ms，真是越来越快了呢～
4.快速排序
快速排序是冒泡的改进，也采用了分治的思想。最差情况时间复杂度也是O(n^2)，平均时间复杂度为O(nlogn)。
上代码，注意，这里的代码采用递归的方式实现
@Test public void sort(){ int []array = new int[200000]; Random random = new Random(); for (int i =0;i < 200000;i++){ array[i]= random.nextInt(900000); } //实现 quicksort(array,0,array.length-1); log.info(Arrays.toString(array)); } void quicksort(int[] array, int left, int right){ if (left>=right){ return; } int i = left;//左哨兵 int j = right;//右哨兵 int index = array[left];//采用第一个元素作为基准 while (i<j){ while (i<j && array[j]>=index){//右边的要全部大于基准，否则跳出循环 j--; } while (i<j && array[i]<=index){//左边的要全部小于基准，否则跳出循环 i++; } swap(array,i,j);//交换左右哨兵的值 } swap(array,left,i);//将基准数放到哨兵相遇的位置，这样基准左边的全部小于它，右边的全部大于它，递归的执行就能完成排序 quicksort(array,left,i-1); quicksort(array,i+1,right); }
20w的数据执行485ms
5.堆排序
堆排序是采用了堆这种数据结构而产生的算法，他的最坏最好的时间复杂度均为O(nlogn)，也是不稳定排序。首先，堆是一个顺序存储的完全二叉树，每个结点的值都大于叶子的值则为大根堆，反之则为小根堆。
它的性质如下：如果根结点索引为i，左孩子为2i+1，右孩子为2i+2。它的第一个非叶子结点为i/2-1.
堆排序的主要流程为：首先将一个无序数组转换为大根堆（或小根堆，取决于降序还是升序）。转换好之后，将第一个结点和最后一个结点交换，然后固定最后一个结点，这样除开最后一个结点外的堆有可能不符合大根堆（或小根堆），所以要将它再次变为大根堆（或小根堆），重复这个过程直至整个堆的根结点，排序也就结束了。根据这个流程，我们需要写两个方法，一个就是将局部堆转换为大根堆（或小根堆），另一个就是遍历整个堆。
下面是它的代码实现：
@Test public void sort(){ int []array = new int[200000]; Random random = new Random(); for (int i =0;i < 200000;i++){ array[i]= random.nextInt(90000000); } //实现 heapsort(array); log.info(Arrays.toString(array)); } //堆排序 void heapsort(int []arr){ //1.构建大顶堆 for(int i=arr.length/2-1;i>=0;i--){//arr.length/2-1代表第一个非叶子结点 //从第一个非叶子结点从下至上，从右至左调整结构 headAdjust(arr,i,arr.length); } //2.调整堆结构+交换堆顶元素与末尾元素 for(int j=arr.length-1;j>0;j--){ swap(arr,0,j);//将堆顶元素与末尾元素进行交换 headAdjust(arr,0,j);//重新对堆进行调整 } } //注意，该方法仅调整堆的局部 private static void headAdjust(int[] arr, int i, int len) {//i为非叶子结点 int tmp = arr[i];//保存这个时候结点的值，相当于挖一个坑，后面让符合条件的孩子来填补 for (int k = 2*i+1; k < len ;k = 2*k+1){//k为该非叶子结点的左孩子，k=2k+1是为了遍历该结点下的左孩子 if (k+1<len && arr[k]<arr[k+1]){//相当于筛选出左右孩子里最大的那个孩子 k++; } if (arr[k] > tmp){//若孩子比父结点的值大，则将孩子的值移到父结点，然后让i指向该孩子 arr[i] = arr[k]; i = k; } } arr[i] = tmp;//这里的i指向孩子 }
20w的数据耗时537ms
总结：堆排序算法主要是针对非叶子结点的排序，从第一个非叶子结点（从下往上）开始，循环每一个非叶子结点后就能得到排好序后的数组了
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://yundeesoft.com/30130.html
