• 七大排序算法

     排序：排序就是对某项数据按照特定的要求，比如大小或字符长短等按照升序或降序排序。

    排序过程中设计稳定性，稳定性指的是若有两个相同的数字，比如1和1。如果排序前1在1的前面，排完序后1还在1的前面。那么就说这个排序算法是稳定的，相反则说明不稳定。

    注意：如果本身就是一个稳定的排序，可以将其变成不稳定排序；如果本身就是不稳定排序，不能变成稳定的排序。

    常见的排序方法

    上面是基于比较的排序。

    下面一个一个的分析

    一：直接插入排序

    直接插入排序指的是将新的数据插入在已经排好序的序列中。比如我们生活中的玩的斗地主，我们需要将新摸的牌按照大小顺序插入到已经排好的扑克牌中。

    例如，将无序的整形数组进行排序：

    思路：

    1.首先判断数组的长度，长度<=1，直接返回

    2.将数组第i(>=1)个下标位置的元素放在temp中

    3.将j下标位置的元素与temp比较。当小于时退出循环，执行4；当大于时，将j位置的元素赋给j+1，然后j--，然后重复这一步直到退出循环(退出循环的结果有两种)

    4.将temp的位置赋给j+1下标的值

    1. public class Insertsort {
    2.     public static void insertsort(int[] array){
    3.         for (int i = 1; i < array.length; i++) {
    4.             int temp = array[i];
    5.             int j = i-1;
    6.             for (; j >=0 ; j--) {
    7.                 if(array[j]<temp){
    8.                     break;
    9.                 }else{
    10.                     array[j+1] = array[j];
    11.                 }
    12.             }
    13.             array[j+1] = temp;
    14.         }
    15.     }
    16.     public static void main(String[] args) {
    17.         int[] array = new int[]{2,5,1,3,11,0,4,-1,-5,7};
    18.         System.out.println("排序前"+ Arrays.toString(array));
    19.         insertsort(array);
    20.         System.out.println("排序后"+ Arrays.toString(array));
    21.     }
    22. }

    直接插入排序总结：

    1.直接插入排序的时间复杂度：O(N^2)(将逆序的数据排成顺序)、O(N)(数据本身就是有序的)

    2.直接插入排序的空间复杂度O(1)

    3.直接插入排序适用于数据量小且数据本身趋于有序的情况

    4.直接插入排序是一种稳定排序算法 

    二：希尔排序

    希尔排序又叫做缩小增量排序，他是直接排序的一种优化。

    它的优化逻辑是将一组无序的序列分成若干组gap，然后将每组进行直接插入排序。最终将gap等于1时所得到的序列再进行一次直接插入排序。gap>1时的排序称为预排序，它的作用是每次直接插入排序完后的序列都更趋近于有序，让整个排序的时间减少。

    我们知道直接插入排序的最坏时间复杂度为O(N^2)，N是序列中元素的个数。现在假设有10000个无序的数据，如果直接插入排序，所需时间为100,000,000。现在将这些数据分成100组，每组100个数据，每组如果采用直接插入排序，需要时间为10000，那么100组所需时间就为1,000,000。所花时间整整降低了100倍。

    希尔排序就是用到的上面的逻辑。

    例如，将无序的整形数组进行排序：

    思路参照下面图片

    1. public class Shellsort {
    2.     public static void shell(int[] array,int gap){
    3.         for (int i = gap; i < array.length; i++) {
    4.             int temp = array[i];
    5.             int j = i-gap;
    6.             for (; j >=0 ; j-=gap) {
    7.                 if(array[j]<temp){
    8.                     break;
    9.                 }else{
    10.                     array[j+gap] = array[j];
    11.                 }
    12.             }
    13.             array[j+gap] = temp;
    14.         }
    15.     }
    16.     public static void shellsort(int[] array){
    17.         int gap = array.length;
    18.         while(gap>1){
    19.             shell(array,gap);
    20.             gap/=2;
    21.         }
    22.         shell(array,1);
    23.     }
    24.     public static void main(String[] args) {
    25.         int[] array = new int[]{2,5,1,3,11,0,4,-1,-5,7};
    26.         System.out.println("排序前"+ Arrays.toString(array));        
    27.         System.out.println("排序后"+ Arrays.toString(array));
    28.     }
    29. }

     

    再来比较一下希尔排序所需时间和直接排序所需时间的比对 

    1. public class Insertsort {
    2.     public static void insertsort(int[] array){
    3.         for (int i = 1; i < array.length; i++) {
    4.             int temp = array[i];
    5.             int j = i-1;
    6.             for (; j >=0 ; j--) {
    7.                 if(array[j]<temp){
    8.                     break;
    9.                 }else{
    10.                     array[j+1] = array[j];
    11.                 }
    12.             }
    13.             array[j+1] = temp;
    14.         }
    15.     }
    16.     public static void main(String[] args) {
    17.         int[] array = new int[100000];
    18.         Random random = new Random();
    19.         for (int i = 0; i < array.length; i++) {
    20.             array[i] = random.nextInt(100000);
    21.         }
    22.         long startime = System.currentTimeMillis();
    23.         insertsort(array);
    24.         long endtime = System.currentTimeMillis();
    25.         System.out.println("直接插入排序算法执行时间"+(endtime-startime));
    26.     }
    27. }

    1. public class Shellsort {
    2.     public static void shell(int[] array,int gap){
    3.         for (int i = gap; i < array.length; i++) {
    4.             int temp = array[i];
    5.             int j = i-gap;
    6.             for (; j >=0 ; j-=gap) {
    7.                 if(array[j]<temp){
    8.                     break;
    9.                 }else{
    10.                     array[i] = array[j];
    11.                 }
    12.             }
    13.             array[j+gap] = temp;
    14.         }
    15.     }
    16.     public static void shellsort(int[] array){
    17.         int gap = array.length;
    18.         while(gap>1){
    19.             shell(array,gap);
    20.             gap/=2;
    21.         }
    22.         shell(array,1);
    23.     }
    24.     public static void main(String[] args) {
    25.         int[] array = new int[100000];
    26.         Random random = new Random();
    27.         for (int i = 0; i < array.length; i++) {
    28.             array[i] = random.nextInt(100000);
    29.         }
    30.         long startime = System.currentTimeMillis();
    31.         shellsort(array);
    32.         long endtime = System.currentTimeMillis();
    33.         System.out.println("希尔排序算法执行时间"+(endtime-startime));
    34.     }
    35. }

     

    可以看到希尔排序明显快直接排序很多。

    希尔排序总结：

    1.希尔排序是对直接插入排序的优化

    2.希尔排序中gap的取法很多，但是我们一般都取序列长度的一半或者按照质素来取。

    3.希尔排序的时间复杂度：O(n^1.25)~O(1.6*n^1.25)

    4.希尔排序是不稳定排序 

    三：选择排序

    选择排序：每次从序列中选出最小(或最大)的一个元素，存放在序列的起始位置；然后再找出序列中次小(或次大)的元素，存放到序列起始的次位置；直到全部待排序的数据 完成排序。

    选择排序类似我们生活中的玩扑克牌，一次性排序17张牌。

    例如，将无序的整形数组进行排序：

    思路：

    1.创建一个零时变量minIndex，让minIndex记录i下标

    2.遍历数组，找到最小(最大)的一个数的下标j，将minIndex记录为j。如果这个最小的数就是第一个(或最后一个)数，就不动，否者让minIndex下标的数和第一个数交换。

    3.i++，重复1~3直到i>array.length

    1. public class Selectsort {
    2.     public static void selectSort(int[] array) {
    3.         for (int i = 0; i < array.length; i++) {
    4.             int minIndex = i;
    5.             for (int j = i + 1; j < array.length; j++) {//内层循环走完以后，minIndex一定最小元素的下标
    6.                 if (array[minIndex] > array[j]) minIndex = j;
    7.             }
    8.             if (array[i] == array[minIndex]) {//说明i下标这个位置的元素就是最小的
    9.                 continue;
    10.             } else {
    11.                 int temp = array[i];
    12.                 array[i] = array[minIndex];
    13.                 array[minIndex] = temp;
    14.             }
    15.         }
    16.     }
    17.     public static void main(String[] args) {
    18.         int[] array = new int[]{2,5,1,3,11,0,4,-1,-5,7};
    19.         System.out.println("排序前"+ Arrays.toString(array));
    20.         selectSort(array);
    21.         System.out.println("排序后"+ Arrays.toString(array));
    22.     }
    23. }

    四：堆排序 

    堆排序是指利用堆这种数据结构所设计的一种排序算法， 在排序过程中如果想升序，那么就要建大堆；如果想降序就要建小堆。

    例如，将无序的整形数组进行排序：

    1. public class heapsort {
    2.     public static void swap(int[] array,int x,int y){
    3.         int temp = array[x];
    4.         array[x] = array[y];
    5.         array[y] = temp;
    6.     }
    7.     public static void shiftDown(int[] array,int x,int len){//向下调整
    8.         int parent = x;
    9.         int child = 2*parent+1;
    10.         while (child<len){
    11.             if(child+1<len&&array[child]<array[child+1]){//如果想降序，这里的array[child]>array[child+1]
    12.                 child++;
    13.             }
    14.             if(array[child]>array[parent]){//如果想降序,这里的array[child]<array[parent]
    15.                 swap(array,child,parent);
    16.                 parent = child;
    17.                 child = 2*parent+1;
    18.             }else{
    19.                 break;
    20.             }
    21.         }
    22.     }
    23.     public static void creatHeap(int[] array){
    24.         for (int parent = array.length-2>>1; parent >=0 ; parent--) {
    25.             shiftDown(array,parent,array.length);
    26.         }
    27.     }
    28.     public static void heapSort(int[] array){
    29.         creatHeap(array);//这里完成堆的创建
    30.         int len = array.length-1;//找到最后一个元素的下标
    31.         while(len>=0){//这里完成堆的排序
    32.             swap(array,0,len);
    33.             shiftDown(array,0,len);
    34.             len--;
    35.         }
    36.     }
    37.  
    38.     public static void main(String[] args) {
    39.         int[] array = new int[]{2,5,1,3,11,0,4,-1,-5,7};
    40.         System.out.println("排序前"+ Arrays.toString(array));
    41.         heapSort(array);
    42.         System.out.println("排序后"+ Arrays.toString(array));
    43.     }
    44. }

    再来看一下选择排序和堆排序排序所花的时间，所给的数据量和插入排序、希尔排序一样。

    可以看到选择排序是这四种排序算法中用时最多的，而堆排序是用时最少的。

    总结一下选择排序和堆排序的特点：

    选择：

    1.选择排序的效率很低

    2.时间复杂度O(N^2)，空间复杂度O(1)

    3.不稳定

    堆排序

    1.效率很高

    2.时间复杂度O(N*logN)，空间复杂度O(1)

    3.不稳定 

    五：冒泡排序

    冒泡排序是我们接触编程语言最早的一种排序算法，我们大家都很熟悉，这里就不详讲了。

    例如，将无序的整形数组进行排序：

    1. public class Bubblesort {
    2.     public static void bubbleSort(int[] array){
    3.         int len = array.length-1;
    4.         for (int i = len; i >0 ; i--) {
    5.             boolean flag = true;
    6.             for (int j = 0; j < i; j++) {
    7.                 if(array[j]>array[j+1]){
    8.                     int temp = array[j];
    9.                     array[j] = array[j+1];
    10.                     array[j+1] = temp;
    11.                     flag = false;
    12.                 }
    13.             }
    14.             if(flag)break;
    15.         }
    16.     }
    17.     public static void main(String[] args) {
    18.         int[] array = new int[]{2,5,1,3,11,0,4,-1,-5,7};
    19.         System.out.println("排序前"+ Arrays.toString(array));
    20.         bubbleSort(array);
    21.         System.out.println("排序后"+ Arrays.toString(array));
    22.     }
    23. }

    再来看一下冒泡排序算法所花时间，数据量同前面一样

      

    可以看到冒泡排序是目前所有排序算法中用时最多的一种排序算法，所以效率极低。 

    冒泡排序的特点总结

    1.冒泡排序算法很容易理解和掌握，但是它在处理一组很大无序的数据时效率极低。

    2.时间复杂度O(N^2)——将逆序转成顺序，O(1)——本身就有序，空间复杂度O(1)

    3.是一种稳定的排序

    六：快速排序

     快速排序是一种基于二叉树结构的交换排序方法，其思想是：任取待排序元素序列中的元素作为基准值，按照该排序码将待排序集合分割成两个子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

    将区间按照基准值分为左右两半部分的常见方式有：

    1.Hoare版

     例如，将无序的整形数组进行排序：

    思路：

    左边第一个元素做基准值key，右边先走(避免left、right相遇时，该位置的元素大于基准值)

    (1)定义left、right并附上相应的下标，以left下标所对应的元素为基准

    (2)左边的left向右走，右边的right向左走。left找到比基准值大的停下来，right找到比基准值小的停下来。交换此时left、right下标所对应的元素，交换以后继续找。

    (3)当left>=right时，让此时left下标的元素和基准值交换。交换以后，以left下标右边和左边为新的待排序数组继续执行1~3，直到整个数组完成排序。

    1. public class HoareSort {
    2.     public static void swap(int[] array,int x,int y){
    3.         int temp = array[x];
    4.         array[x] = array[y];
    5.         array[y] = temp;
    6.     }
    7.  
    8.     public static int quickSort(int[] array,int left,int right){
    9.         int keyIndex = left;
    10.         int temp = array[left];
    11.         while(left<right){
    12.             while(left<right && array[right]>=temp){//执行完这个循环出去的一定是小于等于temp的元素
    13.                 right--;
    14.             }
    15.             while(left<right&&array[left]<=temp){//执行完这个循环出去的一定是大于等于temp的元素
    16.                 left++;
    17.             }
    18.             swap(array,left,right);
    19.         }
    20.         swap(array,keyIndex,left);
    21.         return left;
    22.     }
    23.  
    24.     public static void hoareSort(int[] array,int left,int right){
    25.         if(left>=right)return;
    26.         int pivot = quickSort(array,left,right);
    27.         hoareSort(array,left,pivot-1);
    28.         hoareSort(array,pivot+1,right);
    29.     }
    30.  
    31.     public static void main(String[] args) {
    32.         int[] array = new int[]{2,5,1,3,11,0,4,-1,-5,7};
    33.         System.out.println("排序前"+ Arrays.toString(array));
    34.         hoareSort(array,0,array.length-1);
    35.         System.out.println("排序后"+ Arrays.toString(array));
    36.     }
    37. }

     再来看一下这六种排序算法测试同一组大数据所花的时间

    因为快速排序和堆排序都是基于二叉树结构的排序算法，所以他们所用的时间差不多。

    但是注意

    Hoare版本的快排如果序列本来就是有序的，那么如果样本数量很大，就会造成栈溢出

    1.         int[] array = new int[100000];
    2.         Random random = new Random();
    3.         for (int i = 0; i < array.length; i++) {
    4.             array[i] = random.nextInt(100000);
    5.         }
    6.         hoareSort(array,0,array.length-1);//先让快速排序将无序的序列变成有序
    7.         long startime = System.currentTimeMillis();
    8.         hoareSort(array,0,array.length-1);//快速排序排序有序序列
    9.         long endtime = System.currentTimeMillis();
    10.         System.out.println("快速排序算法执行时间"+(endtime-startime));

      

    2.挖坑法写快速排序

    思路：

    (1)定义left、right并赋上相应的下标，记录当前left下标所对应的元素为temp

    (2)左边的left向右走、右边的right向左走。right先走，right找到比temp小的值停下来，将right所在位置的元素赋给left所在的位置。left找到比temp大的值停下来，将left所在位置的元素赋给right所在的位置。

    (3)当left>=right时，将temp的值赋给left所在的位置，返回left 

    (4)以left下标右边和左边为新的待排序数组继续执行1~3，直到整个数组完成排序。

    1. class QuickSort{
    2.     public static int quickSort2(int[] array, int left, int right) {
    3.         int temp = array[left];
    4.         while (left < right) {
    5.             while (left < right && array[right] >= temp) {//执行完这个循环出去的一定是小于等于temp的元素
    6.                 right--;
    7.             }
    8.             array[left] = array[right];
    9.             while (left < right && array[left] <= temp) {//执行完这个循环出去的一定是大于等于temp的元素
    10.                 left++;
    11.             }
    12.             array[right] = array[left];
    13.         }
    14.         array[left] = temp;
    15.         return left;
    16.     }
    17.     public void digHole(int[] array,int left,int right){
    18.         if(left>=right)return;
    19.         int pivot = quickSort2(array,left,right);
    20.         digHole(array,left,pivot-1);
    21.         digHole(array,pivot+1,right);
    22.     }
    23. }
    24. public class HoareSort {
    25.     public static void main(String[] args) {
    26.         QuickSort quickSort = new QuickSort();
    27.         int[] array = new int[]{2,5,1,3,11,0,4,-1,-5,7};
    28.         System.out.println("排序前"+ Arrays.toString(array));
    29.         quickSort.digHole(array,0,array.length-1);
    30.         System.out.println("排序后"+ Arrays.toString(array));
    31.     }
    32. }

    3.前后指针法

    思路：

    (1)记录序列左边第一个数为temp，第二个数为cur

    (2)从序列左边第二个数(下表为i)开始，比较它和temp的大小关系，若小于，则让cur下标的数和i下标的数交换，同时cur++；若大于，则让i++。重复执行(2)直到i>right退出循环

    (3)让temp与cur-1下标位置的数交换，返回cur-1

    (4)以(3)返回的结果分成左右两个子序列，重复1~4直到将序列排成有序

    1.     public int quickSort3(int[] array, int left,int right) {
    2.         int temp = array[left];
    3.         int cur = left + 1;
    4.         for (int i = left + 1; i <=right; i++) {
    5.             if (array[i] < temp) {
    6.                 swap(array, i, cur);
    7.                 cur++;
    8.             }
    9.         }
    10.         swap(array, left, cur - 1);
    11.         return cur - 1;
    12.     }
    13.  
    14.     public void pointer(int[] array,int left,int right){
    15.         if(left>=right)return;
    16.         int pivot = quickSort3(array,left,right);
    17.         pointer(array,left,pivot-1);
    18.         pointer(array,pivot+1,right);
    19.     }
    20. }
    21. public class HoareSort {
    22.     public static void main(String[] args) {
    23.         QuickSort quickSort = new QuickSort();
    24.         int[] array = new int[]{2,5,1,3,11,0,4,-1,-5,7};
    25.         System.out.println("排序前"+ Arrays.toString(array));
    26.         quickSort.pointer(array,0,array.length-1);
    27.         System.out.println("排序后"+ Arrays.toString(array));
    28.     }
    29. }

    快速排序的优化

    通过上面的测试我们发现，当给一组有序且很大的数据时，如果用快速排序就会造成栈溢出，溢出的原因就是因为快速排序在递归的时候要开辟内存空间，而递归的次数受树高度的影响。给定一组有序序列，在快排时就等同于只有左树或者只有右树，这样递归的次数就是这个序列的长度，因此给定的序列越大，递归次数越多就会越容易栈溢出。

    为了解决上面的问题，主要有以下办法

    1.采用混合排序(优化的是区间)——没有根本上解决问题

    采用混合排序也就是先采用快排，让递归达到某个深度以后采用其他排序算法，这样就可以在一定程度上减缓栈溢出的概率

    1. class QuickSort{
    2.     public static void insertsort(int[] array){
    3.         for (int i = 1; i < array.length; i++) {
    4.             int temp = array[i];
    5.             int j = i-1;
    6.             for (; j >=0 ; j--) {
    7.                 if(array[j]<temp){
    8.                     break;
    9.                 }else{
    10.                     array[j+1] = array[j];
    11.                 }
    12.             }
    13.             array[j+1] = temp;
    14.         }
    15.     }
    16.  
    17.     public static void swap(int[] array, int x, int y) {
    18.         int temp = array[x];
    19.         array[x] = array[y];
    20.         array[y] = temp;
    21.     }
    22.     public static int quickSort(int[] array, int left, int right) {
    23.         int keyIndex = left;
    24.         int temp = array[left];
    25.         while (left < right) {
    26.             while (left < right && array[right] >= temp) {//执行完这个循环出去的一定是小于等于temp的元素
    27.                 right--;
    28.             }
    29.             while (left < right && array[left] <= temp) {//执行完这个循环出去的一定是大于等于temp的元素
    30.                 left++;
    31.             }
    32.             swap(array, left, right);
    33.         }
    34.         swap(array, keyIndex, left);
    35.         return left;
    36.     }
    37.     public static void hoareSort(int[] array,int left,int right){
    38.         if(left>=right)return;
    39. //        if(right-left+1<70000){
    40. //            insertsort(array);
    41. //            return;
    42.         }
    43.         int pivot = quickSort(array,left,right);
    44.         hoareSort(array,left,pivot-1);
    45.         hoareSort(array,pivot+1,right);
    46.     }
    47.  
    48. }
    49. public class HoareSort {
    50.     public static void main(String[] args) {
    51.         QuickSort quickSort = new QuickSort();
    52.         int[] array = new int[100000];
    53.         Random random = new Random();
    54.         for (int i = 0; i < array.length; i++) {
    55.             array[i] = random.nextInt(100000);
    56.         }
    57.         quickSort.hoareSort(array,0,array.length-1);//让序列变得有序
    58.         long startime = System.currentTimeMillis();
    59.         quickSort.hoareSort(array,0,array.length-1);
    60.         long endtime = System.currentTimeMillis();
    61.         System.out.println("快速排序算法执行时间"+(endtime-startime));
    62.     }
    63. }

    下面是没有优化的效果

    然后将代码注释处去掉注释以后

    2.采用三数取中法(优化分割区间的方法)——从根本上解决递归深度太深的问题

    思路如下

    1.     public static int getmidIndex(int[] array,int left,int right){
    2.         int mid = left+((right-left)>>1);
    3.         if(array[left]<array[right]){
    4.             if(array[mid]<array[left]){
    5.                 return left;
    6.             }else if(array[mid]>array[right]){
    7.                 return right;
    8.             }else{
    9.                 return mid;
    10.             }
    11.         }else{
    12.             if(array[mid]<array[right]){
    13.                 return right;
    14.             }else if(array[mid]>array[left]){
    15.                 return left;
    16.             }else {
    17.                 return mid;
    18.             }
    19.         }
    20.     }    
    21.  
    22.  
    23.  
    24.     public static void hoareSort(int[] array,int left,int right){
    25.         if(left>=right)return;
    26. //        if(right-left+1<70000){
    27. //            insertsort(array);
    28. //            return;
    29. //        }
    30.  
    31.         int index = getmidIndex(array,left,right);
    32.         swap(array,left,index);
    33.         int pivot = quickSort(array,left,right);
    34.         hoareSort(array,left,pivot-1);
    35.         hoareSort(array,pivot+1,right);
    36.     }

     优化以后的结果

    非递归实现快速排序

    思路见下图

    1. class QuickSort2{
    2.     public static int quickSort(int[] array, int left, int right) {
    3.         int temp = array[left];
    4.         while (left < right) {
    5.             while (left < right && array[right] >= temp) {//执行完这个循环出去的一定是小于等于temp的元素
    6.                 right--;
    7.             }
    8.             array[left] = array[right];
    9.             while (left < right && array[left] <= temp) {//执行完这个循环出去的一定是大于等于temp的元素
    10.                 left++;
    11.             }
    12.             array[right] = array[left];
    13.         }
    14.         array[left] = temp;
    15.         return left;
    16.     }
    17.  
    18.     public static void hoareSort(int[] array,int left,int right){
    19.         Stack<Integer> stack = new Stack<>();
    20.         int pivot = quickSort(array,left,right);
    21.         if(pivot>left+1){
    22.             stack.push(left);
    23.             stack.push(pivot-1);
    24.         }
    25.         if(pivot<right-1){
    26.             stack.push(pivot+1);
    27.             stack.push(right);
    28.         }
    29.         while(!stack.isEmpty()){
    30.             right = stack.pop();
    31.             left = stack.pop();
    32.             pivot = quickSort(array,left,right);
    33.             if(pivot>left+1){
    34.                 stack.push(left);
    35.                 stack.push(pivot-1);
    36.             }
    37.             if(pivot<right-1){
    38.                 stack.push(pivot+1);
    39.                 stack.push(right);
    40.             }
    41.         }
    42.     }
    43.  
    44. }
    45. public class HoareSort2 {
    46.     public static void main(String[] args) {
    47.         QuickSort2 quickSort = new QuickSort2();
    48.         int[] array = new int[]{2,5,1,3,11,0,4,-1,-5,7};
    49.         System.out.println("排序前"+ Arrays.toString(array));
    50.         quickSort.hoareSort(array,0,array.length-1);
    51.         System.out.println("排序后"+ Arrays.toString(array));
    52.     }
    53. }

     再来看一下非递归快速排序，排序所花时间，数据样本和前面的都一样

    将一组有序数据排序

    可以看到效率不如优化后的递归排序

    将无序数据排成有序

    效果也比优化后的递归排序差一点 

    快速排序特点总结：

    1.时间复杂度O(N*logN)——所有的左右子序列刚好是整体序列的一半时

    2.空间复杂度O(logN)——满二叉树的高度

    3.不稳定

    七.归并排序

    归并排序是利用分治算法思想将序列分解成左右两个子序列，让两个子序列有序以后，再将左右子序列合并排序，最终得到一个完全有序的序列。

    思路：

    一个数组一分为二，两边分别排序，排好序后，创建一个数组，将排好序的数字左右两边比较大小，将小的放在新数组中，遇到某边越界以后，将另一边剩下的数全部拷贝到新数组中，最后将数组拷贝回原来的数组。

    具体操作见下图

    1. class Soultion{
    2.     public static void merger(int[] array,int left,int mid,int right){
    3.         int s1 = left;
    4.         int e1 = mid;
    5.         int s2 = mid+1;
    6.         int e2 = right;
    7.         int[] tempArr = new int[right-left+1];
    8.         int k = 0;
    9.         while(s1<=e1 && s2<=e2){
    10.             if(array[s1]<=array[s2]){
    11.                 tempArr[k++] = array[s1++];
    12.             }else{
    13.                 tempArr[k++] = array[s2++];
    14.             }
    15.         }
    16.         while(s1<=e1){
    17.             tempArr[k++] = array[s1++];
    18.         }
    19.         while(s2<=e2){
    20.             tempArr[k++] = array[s2++];
    21.         }
    22.         for (int i = 0; i < tempArr.length; i++) {
    23.             array[i+left] = tempArr[i];
    24.         }
    25.     }
    26.     public static void mergerSortInternall(int[] array,int left,int right){
    27.         if(left>=right)return;
    28.         int mid = left+((right-left)>>>1);
    29.         mergerSortInternall(array,left,mid);
    30.         mergerSortInternall(array,mid+1,right);
    31.         merger(array,left,mid,right);
    32.     }
    33.     public static void mergerSort(int[] array){
    34.         mergerSortInternall(array,0,array.length-1);
    35.     }
    36. }
    37. public class MergerSort {
    38.     public static void main(String[] args) {
    39.         Soultion soultion = new Soultion();
    40.         int[] array = new int[]{2,5,1,3,11,0,4,-1,-5,7};
    41.         System.out.println("排序前"+ Arrays.toString(array));
    42.         soultion.mergerSort(array);
    43.         System.out.println("排序后"+ Arrays.toString(array));
    44.     }
    45. }

     

    非递归实现归并排序 

     思路见下图

    1. class Soultion{
    2.     public static void mergerSortInternall2(int[] array,int left,int right){
    3.         int gap = 1;
    4.         while(gap<array.length){
    5.             for (int i = 0; i < array.length; i+=2*gap) {
    6.                 left = i;
    7.                 int mid = left+gap-1;
    8.                 if(mid>= array.length){
    9.                     mid = array.length-1;
    10.                 }
    11.                 right = mid+gap;
    12.                 if(right>= array.length){
    13.                     right = array.length-1;
    14.                 }
    15.                 merger(array,left,mid,right);
    16.             }
    17.             gap*=2;
    18.         }
    19.     }
    20.     public static void mergerSort(int[] array){
    21.         mergerSortInternall2(array,0,array.length-1);
    22.     }
    23. }
    24. public class MergerSort {
    25.     public static void main(String[] args) {
    26.         Soultion soultion = new Soultion();
    27.         int[] array = new int[]{2,5,1,3,11,0,4,-1,-5,7};
    28.         System.out.println("排序前"+ Arrays.toString(array));
    29.         soultion.mergerSort(array);
    30.         System.out.println("排序后"+ Arrays.toString(array));
    31.     }
    32. }

    非基于比较的排序

    1.计数排序 

    计数排序：统计相同元素出现的次数，根据统计结果将序列回收到原来的序列中

    1. class Soultion{
    2.     public static void countSort(int[] array){
    3.         int maxValue = array[0];
    4.         int minValue = array[0];
    5.         for (int i = 1; i < array.length; i++) {
    6.             if(array[i]>maxValue){
    7.                 maxValue = array[i];
    8.             }
    9.             if(array[i]<minValue){
    10.                 minValue = array[i];
    11.             }
    12.         }
    13.         int reage = maxValue-minValue+1;
    14.         int[] count = new int[reage];
    15.         for (int i = 0; i < array.length; i++) {
    16.             count[array[i]-minValue]++;
    17.         }
    18.         int k = 0;
    19.         for (int i = 0; i < count.length; i++) {
    20.             while(count[i]>0){
    21.                 array[k++] = i+minValue;
    22.                 count[i]--;
    23.             }
    24.         }
    25.     }
    26. }
    27. public class CountSort {
    28.     public static void main(String[] args) {
    29.         Soultion soultion = new Soultion();
    30.         int[] array = new int[]{2,5,1,3,11,0,4,-1,-5,7};
    31.         System.out.println("排序前"+ Arrays.toString(array));
    32.         soultion.countSort(array);
    33.         System.out.println("排序后"+ Arrays.toString(array));
    34.     }
    35. }

     

     计数排序特点总结：

    1.计数排序在数据范围集中时，效率很高，但是适用范围及场景有限

    2.时间复杂度：O(MAX(N，范围))

    3.空间复杂度：O(范围)

    4.是一种稳定的排序

    2.基数排序

    基数排序是依次根据个位数、十位数、百位数......的大小来排序 ，最终的结果就是排好序的序列

    思路：

    1.根据所给序列，找到序列中数据的最大值，并求该值的位数。

    2.创建十个队列，这里可以将队列形象为桶。根据数据每一位的值放在相应桶中

    3.再将桶里面的数据依次取出来

    1. class Soultion_{
    2.     public static int countlen(int data){
    3.         return (data+"").length();
    4.     }
    5.     public static int index(int num,int r){
    6.         int ret = 0;
    7.         for (int i = 1; i <=r ; i++) {
    8.             ret = num%10;
    9.             num/=10;
    10.         }
    11.         return ret;
    12.     }
    13.     public static void sort(int[] array){
    14.         int max = array[0];
    15.         for (int i = 1; i < array.length ; i++) {
    16.             if(array[i]>max)max = array[i];
    17.         }
    18.         int len = countlen(max);
    19.         LinkedList<Integer>[] list = new LinkedList[10];
    20.         for (int i = 0; i < list.length; i++) {
    21.             list[i] = new LinkedList<>();
    22.         }
    23.         for (int i = 1; i <=len ; i++) {
    24.             for (int j = 0; j < array.length; j++) {
    25.                 list[index(array[j],i)].offer(array[j]);
    26.             }
    27.             int k = 0;
    28.             for (int j = 0; j < list.length; j++) {
    29.                 while(!list[j].isEmpty()){
    30.                     array[k++] = list[j].poll();
    31.                 }
    32.             }
    33.         }
    34.     }
    35. }
    36. public class RadixSort {
    37.     public static void main(String[] args) {
    38.         Soultion_ soultion = new Soultion_();
    39.         int[] arr = { 23, 1, 4, 9, 98, 132, 42 };
    40.         soultion.sort(arr);
    41.         System.out.println(Arrays.toString(arr));
    42.     }
    43. }

    基数排序特点总结：

    1.时间复杂度O(n)

    2.当元素取值范围较大，但元素个数较少时可以利用基数排序 

     

    3.桶排序 

    桶排序是根据所给序列中数据来划分区间，一个区间就是一个桶，将元素之间差值不大的放进一个桶中。然后对桶内数据进行排序，最后将排好序的桶内数据倒出给原来的数组。

    思路见下图：

     

    1. class Sort{
    2.     public static void bucketSort(int [] array){
    3.         int max = Integer.MIN_VALUE;
    4.         int min = Integer.MAX_VALUE;
    5.         for (int i = 0; i < array.length; i++) {
    6.             max = Math.max(max,array[i]);
    7.             min = Math.min(min,array[i]);
    8.         }
    9.         int reage = (max-min)/ array.length+1;
    10.         PriorityQueue<Integer>[] queue = new PriorityQueue[reage];
    11.         for (int i = 0; i < reage; i++) {
    12.             queue[i] = new PriorityQueue<>();
    13.         }
    14.         for (int i = 0; i < array.length; i++) {
    15.             int num = (array[i]-min)/array.length;
    16.             queue[num].offer(array[i]);
    17.         }
    18.         int k = 0;
    19.         for (int i = 0; i < queue.length; i++) {
    20.             while(!queue[i].isEmpty()){
    21.                 array[k++] = queue[i].poll();
    22.             }
    23.         }
    24.     }
    25. }
    26. public class BucketSort {
    27.     public static void main(String[] args) {
    28.         Sort sort = new Sort();
    29.         int[] array = new int[]{3,0,19,15,24,30};
    30.         System.out.println("排序前"+ Arrays.toString(array));
    31.         sort.bucketSort(array);
    32.         System.out.println("排序后"+ Arrays.toString(array));
    33.     }
    34. }

     

    桶排序特点总结：

    1.时间复杂度O(N)

    2.空间复杂度O(N+M)

    3.不稳定 

  • 相关阅读:
    2370. 最长理想子序列（每日一难phase2--day6）
    网工知识角|什么是防火墙你知道吗？一篇直接搞懂
    软件过程与建模学习之：Cost Estimation
    K8s: 集群内Pod通信机制之DNS
    《向量数据库指南》——选择向量数据库时需要考量的点Milvus Cloud
    4-6 最小生成树Prim,Kruskal(贪心)
    SpringBoot笔记：SpringBoot集成MybatisPlus、H2纯内存数据库实战
    Linux的七种运行级别
    Android编写一个视频监控App
    第一届龙信杯取证比赛部分题目复现
  • 原文地址：https://blog.csdn.net/yahid/article/details/125413176