程序员不得不知道的排序算法-上

浅浅的花香味﹌ 2024-02-29 01:44 40阅读 0赞

**目录**

前言

1.冒泡排序

2.选择排序

3.插入排序

4.希尔排序

5.快速排序

6.归并排序

总结

--------------------

## 前言 ##

> 今天给大家讲一下常用的排序算法

--------------------

## 1.冒泡排序 ##

冒泡排序（Bubble Sort）是一种简单的排序算法，它重复地从待排序的元素中比较相邻的两个元素，如果它们的顺序错误就交换它们，直到整个序列有序为止。

冒泡排序的基本思想是通过不断交换相邻的元素，将最大（或最小）的元素逐渐“冒泡”到序列的末尾。每一轮冒泡操作都会将当前未排序部分的最大（或最小）元素放到已排序部分的末尾。

![0da065405bb94fbbb664bd2252a143f4.gif][]

![91292c01e51a4446a944de4953f6ced6.png][]

**代码实现**

>     public static void BubbleSort(int[] arr){
>         for (int i = 0; i < arr.length; i++) {
>             for (int j = 0; j < arr.length-1; j++) {
>                 if(arr[j] > arr[j+1]){
>                     swap(arr,j,j+1);
>                 }
>             }
>             System.out.println("第"+(i+1)+"轮");
>             System.out.println(Arrays.toString(arr));
>         }
>     }
>     
>     
>     public static void swap(int[] arr,int i,int j){
>         int temp = arr[i];
>         arr[i] = arr[j];
>         arr[j] = temp;
>     }

![9b62a5dd70bc450caea5e3e1b8e7669e.png][]

看出来了没?,多循环了两次,明明我们后面的已经有序了,就没有必要再进行比较了,基于此可以来改善我们的代码

>     public static void BubbleSort(int[] arr){
>         for (int i = 0; i < arr.length; i++) {
>             boolean flag = false;
>             for (int j = 0; j < arr.length-1 -i; j++) {
>                 if(arr[j] > arr[j+1]){
>                     swap(arr,j,j+1);
>                     flag = true;
>                 }
>             }
>             if(!flag){
>                 break;
>             }
>         }
>     }

定义标志位flag 如果遍历一遍数组,没有发生交换,就说明已经有序了,直接跳出即可

![096d5ea01d0949bda0ebe77609790052.png][]

**时间复杂度:** 冒泡排序的时间复杂度是O(n2)，其中n是待排序数组的长度。冒泡排序的基本思想是通过不断交换相邻的元素，将最大（或最小）的元素逐渐“冒泡”到序列的末尾。每一轮冒泡操作都需要比较和交换n-1次，总共需要进行n-1轮冒泡操作。因此，总的比较和交换次数为(n-1) + (n-2) + ... + 1 = n(n-1)/2，时间复杂度为O(n2)。

**空间复杂度:** 冒泡排序的空间复杂度是O(1)，因为它只需要使用常数级别的额外空间来存储临时变量。

**稳定性:** 冒泡排序是一种稳定的排序算法。稳定性指的是如果两个元素的值相等，排序后它们的相对顺序不会发生改变。在冒泡排序中，只有当相邻两个元素需要交换时才会改变它们的相对顺序，因此相等元素的相对顺序不会发生改变，冒泡排序是稳定的排序算法。

--------------------

## 2.选择排序 ##

选择排序（Selection Sort）是一种简单直观的排序算法，它的基本思想是每次从待排序的元素中选择最小（或最大）的元素，放到已排序部分的末尾。

![c40700ebdabf426aa26f6b29a231e091.gif][]

选择排序的实现步骤如下：

1.  遍历待排序的数组，从第一个元素开始。
2.  在未排序部分中找到最小（或最大）的元素，记录其位置。
3.  将最小（或最大）的元素与当前遍历位置的元素交换位置，将最小（或最大）的元素放到已排序部分的末尾。
4.  重复步骤2和步骤3，直到遍历完整个数组，排序完成。

**代码实现**

>     public static void selectSort(int[] arr){
>         for (int i = 0; i < arr.length; i++) {
>             // 默认认为i下标的元素为最小值
>             int minIndex = i;
>             for (int j = i+1; j < arr.length; j++) {
>                 if(arr[j] < arr[minIndex]){
>                     // 碰见更小的元素,更新minIndex的值
>                     minIndex = j;
>                 }
>             }
>             swap(arr,i,minIndex);
>         }
>     }

![83f92e0f88074a0f804e3627c18cdf10.png][]

**时间复杂度:** 选择排序和冒泡排序的时间复杂度都是O(n^2)，其中n是待排序数组的长度。它们都是基于比较的排序算法，需要进行n(n-1)/2次比较操作。

**空间复杂度:** 选择排序的空间复杂度是O(1)，因为它只需要使用常数级别的额外空间来存储临时变量。

**稳定性:** 选择排序是一种稳定的排序算法。

## 3.插入排序 ##

插入排序是一种简单直观的排序算法，它的基本思想是将待排序的元素插入到已排序部分的合适位置。

![ef2c8d1ee60e408795cced52a093e0eb.png][]

![1362961959b04d72bb5d69993d87d4c3.gif][]

插入排序的步骤如下：

1.  将待排序数组分为已排序部分和未排序部分。**初始时，已排序部分只有一个元素，即数组的第一个元素。**
2.  从未排序部分依次取出一个元素，与已排序部分的元素进行比较。
3.  将该元素插入到已排序部分的合适位置，使得已排序部分仍然保持有序。
4.  重复步骤2和步骤3，直到遍历完整个数组，排序完成。

**代码实现**

>     public static void insertSort(int[] arr){
>         for (int i = 1; i < arr.length; i++) {
>             // 当前要插入的元素
>             int cur = arr[i];
>     
>             int j;
>             for (j = i-1; j >=0; j--) {
>                 if(cur >= arr[j]){
>                     break;
>                 }else{
>                     arr[j+1] = arr[j];
>                 }
>             }
>            arr[j+1] = cur;
>         }
>     }

![bac9d6d883d548ea84eccd53e67d3d21.png][]

**时间复杂度:** 选择排序的时间复杂度是O(n^2)，其中n是待排序数组的长度。在最坏情况下，即待排序数组是逆序的情况下，需要进行n(n-1)/2次比较和n-1次交换操作。

**空间复杂度:** 选择排序的空间复杂度是O(1)，因为它只需要使用常数级别的额外空间来存储临时变量。

**稳定性:** 选择排序是不稳定的排序算法。

直接插入排序的特性总结：

1. 元素集合越接近有序，直接插入排序算法的时间效率越高(应用场景为接近有序的一组数组内进行排序)

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

3. 空间复杂度：O(1)，它是一种稳定的排序算法

4. 稳定性：稳定

--------------------

## 4.希尔排序 ##

希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成多个组， 所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达 =1时，所有记录在统一组内排好序。

>     public static void shellSort(int[] arr){
>         // 分组
>         for (int gap = arr.length/2; gap >= 1; gap = gap/2) {
>             // 遍历每一个分组
>             for (int i = gap; i < arr.length; i++) {
>                 int cur = arr[i];
>                 int j;
>                 for ( j = i - gap; j >=0 ; j-=gap) {
>                     if(arr[j] > cur){
>                         arr[j+gap] = arr[j];
>                     }else{
>                         break;
>                     }
>                 }
>                 arr[j+gap] = cur;
>             }
>         }
>     }

![3fc37e2220f740b5a4a1b2528e04bee4.png][]

希尔排序的特性总结：

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

2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。

3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排 序的时间复杂度都不固定

4. 稳定性：不稳定

--------------------

## 5.快速排序 ##

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

![28e013f8bb944c64a68190b563fc6ebd.gif][]

快速排序的基本步骤如下：

1.  选择一个基准元素（pivot），一般选择数组的第一个元素。
2.  将数组分成两部分，使得左边的元素都小于等于基准元素，右边的元素都大于等于基准元素。这个过程称为分区（partition）。
3.  对左右两部分分别进行快速排序，递归地调用上述步骤。
4.  合并左右两部分，得到最终的排序结果。

**代码实现**

>     public static void quickSort(int[] arr){
>         quick(arr,0,arr.length-1);
>     }
>     public static void quick(int[] arr,int left,int right){
>         if(left >= right){
>             return;
>         }
>         int pivot = partition(arr,left,right);
>     
>         // 向左递归
>         quick(arr,left,pivot-1);
>         // 向右递归
>         quick(arr,pivot+1,right);
>     }
>     
>     // 分区 返回基准下标 方便下一次进行递归
>     // 1. Hoare版
>     private static int partition(int[] arr,int left,int right){
>         int pivot = arr[left];
>         int i = left;
>         int j = right;
>         while (left < right) {
>             while (left < right && arr[right] >= pivot) {
>                 right--;
>             }
>     
>             while (left < right && arr[left] <= pivot) {
>                 left++;
>             }
>             swap(arr, left, right);
>         }
>     // 将基准更新为相遇点
>         swap(arr, left, i);
>         return left;
>     }
> 
> // 2.挖坑法
> 
>     private static int partition2(int[] arr, int left, int right) {
>         int key = arr[left];
>         while(left < right){
>             while(left < right && arr[right] >= key){
>                 right--;
>             }
>             arr[left] = arr[right];
>     
>             while(left < right && arr[left] <= key){
>                 left++;
>             }
>             arr[right] = arr[left];
>         }
>         arr[left] = key;
>         return left;
>     }

hoare法

![4c3b012737d44f0384ebea5cec0942e7.png][]

挖坑法

![59523770644640dca740fd6f3537fa66.png][]**快速排序总结**

1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序

2. 时间复杂度：O(N\*logN)

![938a136c3cd74ef08b916bd6937f3a2d.png][]

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

4. 稳定性：不稳定

--------------------

## 6.归并排序 ##

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

![44a5ecd1d3614261b89fba63a0e16f36.png][]

归并排序的具体步骤如下：

1.  将待排序序列不断地二分，直到每个子序列只有一个元素。
2.  逐层合并相邻的子序列，直到合并成一个完整的有序序列。

**代码实现**

>     public static void mergeSort(int[] arr){
>         mergeSeparate(arr,0,arr.length-1);
>     }
>     // 归
>     public static void mergeSeparate(int[] arr,int left,int right){
>         if(left >= right){
>             return;
>         }
>         int mid = (left+right)/2;
>     
>         mergeSeparate(arr,left,mid);
>         mergeSeparate(arr,mid+1,right);
>         merge(arr,left,right,mid);
>     }
>     // 并
>     public static void merge(int[] arr,int left ,int right,int mid){
>         int[] array = new int[right-left+1];
>         int i = left;
>         int j = mid+1;
>         int k = 0;
>         while(i<=mid && j<=right){
>             while(i<=mid && arr[i] <= arr[j]){
>                 array[k++] = arr[i++];
>             }
>             while(j<=right && arr[j] <= arr[i]){
>                 array[k++] = arr[j++];
>             }
>         }
>         while(i <= mid){
>             array[k++] = arr[i++];
>         }
>         while(j <= mid){
>             array[k++] = arr[j++];
>         }
>     
>         // 将新数组中的元素拷贝到老数组中
>         for (int l = 0; l < array.length; l++) {
>             arr[left++] = array[l];
>         }
>     }

--------------------

## 总结 ##

这篇博客就到这了,大家多理解一下就ok

[0da065405bb94fbbb664bd2252a143f4.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/29/a8f7f457ba73489f9a94e55b8e4ed7d2.png
[91292c01e51a4446a944de4953f6ced6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/29/3d9bddcaeb764b58b2aa45a00313905d.png
[9b62a5dd70bc450caea5e3e1b8e7669e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/29/82500d69dfe34fe18545d49a9a308925.png
[096d5ea01d0949bda0ebe77609790052.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/29/122ccf44e6024775a9e2b389277808ad.png
[c40700ebdabf426aa26f6b29a231e091.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/29/b7830a28b6f34c7faed45f5eca9bcfcd.png
[83f92e0f88074a0f804e3627c18cdf10.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/29/9f66f2f22dc1437a83f066bf322375af.png
[ef2c8d1ee60e408795cced52a093e0eb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/29/8f386986a2384eb1a876500363ac3bff.png
[1362961959b04d72bb5d69993d87d4c3.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/29/bd547a6242ee47fab2c872fb9ad368c8.png
[bac9d6d883d548ea84eccd53e67d3d21.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/29/9b8ebfcc12cf4a1d8e7694f1502bde91.png
[3fc37e2220f740b5a4a1b2528e04bee4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/29/a3d3f301c3134f3ea21829b8c8ec5b02.png
[28e013f8bb944c64a68190b563fc6ebd.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/29/40f04c0348ed461fbc221bc6ca9ff584.png
[4c3b012737d44f0384ebea5cec0942e7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/29/9d1e1cc744c14fdd87f90babef0270f4.png
[59523770644640dca740fd6f3537fa66.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/29/59a3a63d9e494537bb7265d5fc6a5cae.png
[938a136c3cd74ef08b916bd6937f3a2d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/29/c006e05abee44b849cb67b90f5360540.png
[44a5ecd1d3614261b89fba63a0e16f36.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/29/1e251447fe8e4aea98d6be4e802488ab.png