• 十分钟“手撕”七大排序

    前言：可以通过目录来找你需要的排序的源代码。先是解释底层原理，后附带代码。 

    目录

    稳定的概念

    一、插入排序

    二、希尔排序

    三、选择排序

    四、堆排序

    五、冒泡排序

    六、快速排序

    七、归并排序

    八、排序总结 

    额外：计数排序

    稳定的概念

    稳定性：

    相同元素的相对位置排序完没有改变，则为稳定排序。 若排序后相同元素的相对位置发生变化，则为不稳定排序。

    一、插入排序

    原理如下：

    从数据的第2位开始，跟前面的比，找到比该数据小的值插到后面，没有的话插到最前面。

     代码思路：

    从第2位开始记为j，让j++把每一位都插到前面去。然后让j的前一位记为i，i--，让j从i开始往前插入。直到全插完。

    插入排序特性总结：

        1. 元素集合越接近有序，直接插入排序算法的时间效率越高
        2. 时间复杂度：O(N^2)
        3. 空间复杂度：O(1)，它是一种稳定的排序算法
        4. 稳定性：稳定     

    1. //插入排序
    2.     /*
    3.     1. 元素集合越接近有序，直接插入排序算法的时间效率越高
    4.     2. 时间复杂度：O(N^2)
    5.     3. 空间复杂度：O(1)，它是一种稳定的排序算法
    6.     4. 稳定性：稳定
    7.     */
    8.     public void insertSort(int[] arr) {
    9.         for (int i = 1; i < arr.length; i++) {
    10.             int tmp = arr[i];
    11.             int j = i - 1;
    12.             for (; j >= 0; j--) {
    13.                 if (arr[j] > tmp) {
    14.                     arr[j + 1] = arr[j];
    15.                 } else {
    16.                     break;
    17.                 }
    18.             }
    19.             //若j<0时，for循环进不来，所以再次放到0下标
    20.             arr[j + 1] = tmp;
    21.         }
    22.     }

    二、希尔排序

    算法原理：

    实际上就是插入排序的优化！插入排序一个一个插太慢了，这时希尔排序就出来了，把数据分多组，让他们先插入排序，然后缩短组数，再排序，循环，直到排完序。

    代码思路：

    我们先把一组数据总数/2分为gap组，先让gap组排序，然后gap/2，排序 ，循环往复，直到排完。如下图，若gap=2时，我们只需要arr[j]=arr[j+gap]和tmp就能交换插入了，gap=2有2轮，但是剩下一轮就只能再fori一次，若让i++就能交替循环，一次fori就能搞定了。

    希尔排序特性：

      时间复杂度：O(N^1.25)到O(1.6 * N^1.25)（业内还没有准确的，只有个大概的）
      稳定性：不稳定

    1.     //希尔排序
    2.     /*
    3.     *
    4.     * 因为咋们的gap是按照Knuth提出的方式取值的，而且Knuth进行了大量的试验统计，我们暂时就按照：
    5.     * O(N^1.25)到O(1.6 * N^1.25)来算。
    6.       稳定性：不稳定
    7.     * */
    8.     public void shellSort(int[] arr) {
    9.         int gap = arr.length;
    10.         while (gap > 1) {
    11.             gap /= 2;
    12.             shell(gap, arr);
    13.         }
    14.     }
    15.  
    16.     private void shell(int gap, int[] arr) {
    17.         for (int i = gap; i < arr.length; i++) {
    18.             int tmp = arr[i];
    19.             int j = i - gap;
    20.             for (; j >= 0; j -= gap) {
    21.                 if (arr[j] > tmp) {
    22.                     arr[j + gap] = arr[j];
    23.                 } else {
    24.                     break;
    25.                 }
    26.             }
    27.             arr[j + gap] = tmp;
    28.  
    29.         }
    30.     }

    三、选择排序

    原理如下：

    每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元 素排完 。

     代码思路：

    把第一个值作为tmp，然后i++往后循环，如果有小于tmp的就替换tmp，就找到最小的了，把它放到j（j=i+1）里面。for循环走完arr.length就排完序了。

    插入排序特性总结：

    1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用

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

    3. 空间复杂度：O(1)

    4. 稳定性：不稳定

    1.     //选择排序
    2.     /*
    3.     1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
    4.     2. 时间复杂度：O(N^2)
    5.     3. 空间复杂度：O(1)
    6.     4. 稳定性：不稳定
    7.     */
    8.     public void selectSort(int[] arr) {
    9.         for (int i = 0; i < arr.length; i++) {
    10.             int minindex = i;
    11.             for (int j = i + 1; j < arr.length; j++) {
    12.                 if (arr[j] < arr[minindex]) {
    13.                     minindex = j;
    14.                 }
    15.             }
    16.             swap(arr, minindex, i);
    17.  
    18.         }
    19.     }
    20.  
    21.     private void swap(int[] arr, int minindex, int i) {
    22.         int tmp = arr[minindex];
    23.         arr[minindex] = arr[i];
    24.         arr[i] = tmp;
    25.  
    26.     }
    27.  
    28.     //选择排序的优化(最大最小一起判断)
    29.     public void selectSort2(int[] arr) {
    30.         int left = 0;
    31.         int right = arr.length - 1;
    32.         while (left < right) {
    33.             int minindex = left;
    34.             int maxindex = left;
    35.  
    36.             for (int i = left + 1; i <= right; i++) {
    37.                 if (arr[i] < arr[minindex]) {
    38.                     minindex = i;
    39.                 }
    40.                 if (arr[i] > arr[maxindex]) {
    41.                     maxindex = i;
    42.                 }
    43.             }
    44.             swap(arr, minindex, left);
    45.             swap(arr, maxindex, right);
    46.             left++;
    47.             right--;
    48.         }
    49.     }

    四、堆排序

    原理如下：

    因为堆是有顺序的，不是大根堆就是小根堆。就是倒置一下顺序，逆序一下。我们只需要将最后一个排序跟堆首调换一下，然后向下调整，每个都如此，直到排完序。 

     代码思路：

    比如大根堆，只需要将end=arr.length-1的元素和堆首元素交换，然后将堆首元素向下调整（找到两个根最大的那一个根，交换），然后end--。

    插入排序特性总结：

        1. 堆排序使用堆来选数，效率就高了很多。
        2. 时间复杂度：O(N*logN)
        3. 空间复杂度：O(1)
        4. 稳定性：不稳定

    1.     //堆排序
    2.     /*
    3.     1. 堆排序使用堆来选数，效率就高了很多。
    4.     2. 时间复杂度：O(N*logN)
    5.     3. 空间复杂度：O(1)
    6.     4. 稳定性：不稳定
    7.     */
    8.     public void heapSort(int[] arr) {
    9.         createBigHeap(arr);
    10.         int end = arr.length - 1;
    11.         while (end >= 0) {
    12.             swap(arr, 0, end);
    13.             siftDown(0, arr, end);
    14.             end--;
    15.         }
    16.     }
    17.  
    18.     private void createBigHeap(int[] array) {
    19.         for (int parent = (array.length - 1 - 1) / 2; parent >= 0; parent--) {
    20.             siftDown(parent, array, array.length);
    21.         }
    22.     }
    23.  
    24.     private void siftDown(int parent, int[] array, int end) {
    25.         int child = 2 * parent + 1;
    26.         while (child < end) {
    27.             if (child + 1 < end && array[child] < array[child + 1]) {
    28.                 child++;
    29.             }
    30.             //child下标 就是左右孩子最大值的下标
    31.             if (array[child] > array[parent]) {
    32.                 swap(array, child, parent);
    33.                 parent = child;
    34.                 child = 2 * parent + 1;
    35.             } else {
    36.                 break;
    37.             }
    38.         }
    39.     }
    40.     private void swap(int[] arr, int minindex, int i) {
    41.         int tmp = arr[minindex];
    42.         arr[minindex] = arr[i];
    43.         arr[i] = tmp;
    44.  
    45.     }

    五、冒泡排序

    原理如下：

    一趟一趟来，将小的数和大数交换，每一趟都可以将最大的一个数放到最后。所有趟数走完，将排序完成。

     代码思路：

    两层循环，第一层控制趟数为arr.length-1，第二层arr.length-1-i表示一趟中交换的次数。定义一个tmp来交换，如果后面的数比前面的数小，则交换，如果大于，就用大于的这个数和后面交换。

    优化：可能循环一次就排完序了，剩下的就浪费时间了。我们可以定义一个flg，如果一趟下来都不需要交换，证明完成了，结束2层循环。

    插入排序特性总结：

        1. 冒泡排序是一种非常容易理解的排序
        2. 时间复杂度：O(N^2)
        3. 空间复杂度：O(1)
        4. 稳定性：稳定

    1.     //冒泡排序
    2. /*
    3.     1. 冒泡排序是一种非常容易理解的排序
    4.     2. 时间复杂度：O(N^2)
    5.     3. 空间复杂度：O(1)
    6.     4. 稳定性：稳定
    7. */
    8.  
    9.     public void buddleSort(int[] arr) {
    10.         for (int i = 0; i < arr.length - 1; i++) {
    11.             boolean flg = false;
    12.             for (int j = 0; j < arr.length - 1 - i; j++) {
    13.                 if (arr[j] > arr[j + 1]) {
    14.                     swap(arr, j, j + 1);
    15.                     flg = true;
    16.                 }
    17.             }
    18.             if (!flg) {
    19.                 break;
    20.             }
    21.         }
    22.     }

    六、快速排序

    原理如下：

    找基准，通常是第一个元素，然后小于它的放左边，大于他的放右边。然后下一组又是这一组的第一个，直到所有元素都排完序。

     代码思路：

    1.递归：每次递归都找第一个为基准，然后<基准，放左边；>基准放右边。直到start

    2.非递归：

    1. 将待排序的序列的首尾元素的下标入栈。
    2. 当栈不为空时，取出栈顶的下标，将序列的首尾元素作为基准值进行分区操作。
    3. 分区操作的目的是将比基准值小的元素放到基准值的左边，比基准值大的元素放到基准值的右边，并返回基准值的下标。
    4. 将分区操作后的左右子序列的首尾元素的下标入栈，注意先将右子序列的下标入栈，再将左子序列的下标入栈。
    5. 重复步骤2-4，直到栈为空。

    优化：

    1. 三数取中法选key

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

    插入排序特性总结：

        1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
        2. 时间复杂度：O(N*logN)
        3. 空间复杂度：O(logN)
        4. 稳定性：不稳定

     

     递归

    1.     //快速排序
    2.     /*
    3.     1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
    4.     2. 时间复杂度：O(N*logN)
    5.     3. 空间复杂度：O(logN)
    6.     4. 稳定性：不稳定
    7. */
    8.  
    9.  
    10.     public void quickSort(int[] arr) {
    11.         quick(arr, 0, arr.length - 1);
    12.     }
    13.  
    14.     public void quick(int[] arr, int start, int end) {
    15.  
    16.         if (start >= end) {
    17.             return;
    18.         }
    19.         if (end - start + 1 <= 10) {
    20.             insertSortRange(arr, start, end);
    21.             return;
    22.         }
    23.  
    24.         //三数取中(优化)
    25.         int index = midThreeNum(arr, start, end);
    26.         swap(arr, index, start);
    27.         int par = partition(arr, start, end);
    28.         quick(arr, start, par - 1);
    29.         quick(arr, par + 1, end);
    30.     }
    31.  
    32.     public static void insertSortRange(int[] array, int left, int right) {
    33.         for (int i = left + 1; i <= right; i++) {
    34.             int tmp = array[i];
    35.             int j = i - 1;
    36.             for (; j >= left; j--) {
    37.                 if (array[j] > tmp) {
    38.                     array[j + 1] = array[j];
    39.                 } else {
    40.                     break;
    41.                 }
    42.             }
    43.             array[j + 1] = tmp;
    44.         }
    45.     }
    46.  
    47.     public int partitionHoard(int[] arr, int left, int right) {
    48.         int tmp = arr[left];
    49.         int i = left;
    50.         while (left < right) {
    51.             while (left < right && arr[right] >= tmp) {
    52.                 right--;
    53.             }
    54.             while (left < right && arr[left] <= tmp) {
    55.                 left++;
    56.             }
    57.             swap(arr, left, right);
    58.         }
    59.         swap(arr, left, i);
    60.         return left;
    61.     }
    62.  
    63.     //挖坑法
    64.     public int partition(int[] arr, int left, int right) {
    65.         int tmp = arr[left];
    66.         while (left < right) {
    67.             while (left < right && arr[right] >= tmp) {
    68.                 right--;
    69.             }
    70.             arr[left] = arr[right];
    71.             while (left < right && arr[left] <= tmp) {
    72.                 left++;
    73.             }
    74.             arr[right] = arr[left];
    75.         }
    76.         arr[left] = tmp;
    77.         return left;
    78.     }
    79.  
    80.     //返回值是中位数的下标(优化快排)
    81.     private static int midThreeNum(int[] array, int left, int right) {
    82.         int mid = (left + right) / 2;
    83.         if (array[left] < array[right]) {
    84.             if (array[mid] < array[left]) {
    85.                 return left;
    86.             } else if (array[mid] > array[right]) {
    87.                 return right;
    88.             } else {
    89.                 return mid;
    90.             }
    91.         } else {
    92.             if (array[mid] < array[right]) {
    93.                 return right;
    94.             } else if (array[mid] > array[left]) {
    95.                 return left;
    96.             } else {
    97.                 return mid;
    98.             }
    99.         }
    100.     }

    非递归 

    1.    //非递归快速排序
    2.     public void quickSortNor(int[] arr) {
    3.         Stack stack = new Stack<>();
    4.         int left = 0;
    5.         int right = arr.length - 1;
    6.         int par = partition(arr, left, right);
    7.         if (par > left + 1) {
    8.             stack.push(left);
    9.             stack.push(par - 1);
    10.         }
    11.         if (par < right - 1) {
    12.             stack.push(par + 1);
    13.             stack.push(right);
    14.         }
    15.         while (!stack.isEmpty()) {
    16.             right = stack.pop();
    17.             left = stack.pop();
    18.             par = partition(arr, left, right);
    19.             if (par > left + 1) {
    20.                 stack.push(left);
    21.                 stack.push(par - 1);
    22.             }
    23.             if (par < right - 1) {
    24.                 stack.push(par + 1);
    25.                 stack.push(right);
    26.             }
    27.         }
    28.     }

    七、归并排序

    原理如下：

    将一组数据递归分成2对，4对....直到分成单一的元素。最后一对一对排序后回来...4对，2对，1对给它排序，直到排完序。

     代码思路：

    递归把数据都分成单一的元素，然后合并，合并的话需要创建一个新的数组tmp，定义s1，e1，s2，e2表示分成2份的数组的头和尾，让s1和s2比较，如果s1比s2小，让s1进入tmp数组，否则反之。若一份数组走完了，另一份数组没有，则让另一份数组while循环进入tmp。

    插入排序特性总结：

        1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
        2. 时间复杂度：O(N*logN)
        3. 空间复杂度：O(N)
        4. 稳定性：稳定

    1.     //合并排序
    2. /*
    3.     1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
    4.     2. 时间复杂度：O(N*logN)
    5.     3. 空间复杂度：O(N)
    6.     4. 稳定性：稳定
    7.     */
    8.     public void mergeSort(int[] arr) {
    9.         mergeSortFun(arr, 0, arr.length - 1);
    10.     }
    11.  
    12.     public void mergeSortFun(int[] arr, int left, int right) {
    13.         if (left >= right) {
    14.             return;
    15.         }
    16.         int mid = (right + left) / 2;
    17.         mergeSortFun(arr, left, mid);
    18.         mergeSortFun(arr, mid + 1, right);
    19.         //合并
    20.         merge(arr, left, mid, right);
    21.     }
    22.  
    23.     private void merge(int[] arr, int left,
    24.                        int mid, int right) {
    25.         int k = 0;
    26.         int[] tmp = new int[right - left + 1];
    27.         int s1 = left;
    28.         int e1 = mid;
    29.         int s2 = mid + 1;
    30.         int e2 = right;
    31.         while (s1 <= e1 && s2 <= e2) {
    32.             if (arr[s1] <= arr[s2]) {
    33.                 tmp[k++] = arr[s1++];
    34.             } else {
    35.                 tmp[k++] = arr[s2++];
    36.             }
    37.         }
    38.         while (s1 <= e1) {
    39.             tmp[k++] = arr[s1++];
    40.         }
    41.         while (s2 <= e2) {
    42.             tmp[k++] = arr[s2++];
    43.         }
    44.         //拷贝
    45.         for (int i = 0; i < k; i++) {
    46.             arr[i + left] = tmp[i];
    47.         }
    48.     }
    49.  
    50.  
    51.     //合并排序非递归
    52.     public void mergeSortNor(int[] array) {
    53.         int gap = 1;
    54.         while (gap < array.length) {
    55.             for (int i = 0; i < array.length; i = i + 2 * gap) {
    56.                 int left = i;
    57.                 int mid = left + gap - 1;
    58.                 if (mid >= array.length) {
    59.                     mid = array.length - 1;
    60.                 }
    61.                 int right = mid + gap;
    62.                 if (right >= array.length) {
    63.                     right = array.length - 1;
    64.                 }
    65.                 merge(array, left, mid, right);
    66.             }
    67.             gap *= 2;
    68.         }
    69.     }

    八、排序总结 

    排序方法最好平均最坏时间复杂度空间复杂度
    冒泡排序O(N)O(N^2)O(N^2)O(1)稳定
    插入排序O(N)O(N^2)O(N^2)O(1)稳定
    选择排序O(N^2)O(N^2)O(N^2)O(1)不稳定
    希尔排序O(N)O(N^1.3)O(n^2)O(1)不稳定
    堆排序O(N * log(N))O(N * log(N))O(N * log(N))O(1)不稳定
    快速排序O(N * log(N))O(N * log(N))O(N^2)O(log(N)) ~ O(N)不稳定
    归并排序O(N * log(N))O(N * log(N))O(N * log(N))O(N)稳定

    额外：计数排序

    1.     //计数排序
    2. /*
    3.     1. 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。
    4.     2. 时间复杂度：O(MAX(N,范围))
    5.     3. 空间复杂度：O(范围)
    6.     4. 稳定性：稳定
    7.     */
    8.  
    9.     public void countSort(int[] array) {
    10.         //1. 遍历数组 求最大值 和 最小值
    11.         int maxVal = array[0];
    12.         int minVal = array[0];
    13.         for (int i = 0; i < array.length; i++) {
    14.             if (maxVal < array[i]) {
    15.                 maxVal = array[i];
    16.             }
    17.             if (minVal > array[i]) {
    18.                 minVal = array[i];
    19.             }
    20.         }
    21.         //2. 定义count数组
    22.         int[] count = new int[maxVal - minVal + 1];
    23.         //3. 遍历array数组 把值 放入 计数数组当中
    24.         for (int i = 0; i < array.length; i++) {
    25.             int val = array[i];//98
    26.             count[val - minVal]++;
    27.         }
    28.         //4. 以上3步完成之后，计数数组 已经存好了对应的数据
    29.         // 接下来 开始遍历 计数数组
    30.         int index = 0;//array的下标
    31.         for (int i = 0; i < count.length; i++) {
    32.             while (count[i] > 0) {
    33.                 array[index] = i + minVal;
    34.                 index++;
    35.                 count[i]--;
    36.             }
    37.         }
    38.     }

  • 相关阅读:
    vulnhub靶场 Kioptrix-level-1
    JS实现发布/订阅
    【自然语言处理】实验3，文本情感分析
    docker 常用命令
    FineBI产品简介
    Vue实战篇三十三：实现新闻的浏览历史
    数据结构二叉树前序遍历递归和非递归算法
    计算机毕业设计（附源码）python装修服务分析系统
    qt5 窗口启动居中显示
    使用ExcelJS快速处理Node.js爬虫数据
  • 原文地址：https://blog.csdn.net/2301_80958683/article/details/140446609