八大排序图解算法

Bertha 。 2023-02-12 14:24 24阅读 0赞

> 其实八大排序如果弄清楚它们的原理并不难，虽然里面有几种排序写起来也很麻烦。  
> 但是最难的往往就是，我们会把它们相互混淆，我给每个排序画了一张动图，看图记忆就好很多了。  
>   
> 每种排序都有相对应的解释和图，大家可以看完解释和图然后按照自己的思路去写代码。(当然也提供了测试好的代码)  
>   
> 末尾提供了测试代码，你只需要改动一行代码，就可以测试你的排序是否正确，如果错误会打印出**原本序列**、**你的排序**、**正确的排序**，以帮助你更好的排错。

**稳定性**：如果一组待排序的数字中，有两个相同的数字。在完成排序后，这两个数字的相对位置不变，即该排序是稳定排序。

**不稳定的排序算法**：堆排序、快速排序、希尔排序、直接选择排序.

**0（nlogn）** 快速排序、堆排序、归并排序，快速排序最好

初始顺序对排序没有影响的是 堆排序

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RvbXdpbGRib2Fy_size_16_color_FFFFFF_t_70]

## 一、冒泡排序 ##

<table> 
 <thead> 
  <tr> 
   <th>平均时间复杂度</th> 
   <th>最好时间复杂度</th> 
   <th>最坏时间复杂度</th> 
   <th>空间复杂度</th> 
   <th>稳定性</th> 
   <th>类别</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>O(n<sup>2</sup>)</td> 
   <td>O(n)</td> 
   <td>O(n<sup>2</sup>)</td> 
   <td>O(1)</td> 
   <td>稳定</td> 
   <td>交换排序</td> 
  </tr> 
 </tbody> 
</table>

### 1-1：冒泡排序的解释 ###

> 循环遍历 0-length-1 的元素，找到最合适每个位置的元素。  
> 把位置 i 的元素和i后面的的每个元素对比，找到最小的元素放在 i 这个位置。（找最大还是最小取决你怎么排序）  
> 下面是图示：

![在这里插入图片描述][20200526144133752.gif]

### 1-2：冒泡排序代码 ###

public void bubbleSort(int[] arr){ 
        int tmp;
        for (int i = 0;i < arr.length - 1; i++){ 
            for (int j = i+1; j < arr.length; j++){ 
                if (arr[i] > arr[j]){ 
                    tmp = arr[j];
                    arr[j] = arr[i];
                    arr[i] = tmp;
                }
            }
        }
    }

## 二、快速排序 ##

<table> 
 <thead> 
  <tr> 
   <th>平均时间复杂度</th> 
   <th>最好时间复杂度</th> 
   <th>最坏时间复杂度</th> 
   <th>空间复杂度</th> 
   <th>稳定性</th> 
   <th>类别</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>O(nlog<sub>2</sub>n)</td> 
   <td>O(nlog<sub>2</sub>n)</td> 
   <td>O(n<sup>2</sup>)</td> 
   <td>O(nlog<sub>2</sub>n)</td> 
   <td>不稳定</td> 
   <td>交换排序</td> 
  </tr> 
 </tbody> 
</table>

### 2-1：快速排序的解释 ###

> 每次选择一个数作为标准，然后比它大的放在右边，比它小的放在左边。  
> 通过上面的操作把数组分成了两份，然后每份继续重复这样的操作，直到排序好。  
>   
> 注：  
> 1、为了方便，这个标准数，我们每次取第一个数  
> 2、当左边长度是1的时候就是排序好了。（同理右边也是）

![在这里插入图片描述][2020052614414658.gif]

### 2-2：快速排序代码 ###

public static void  quickSort(int[] arr,int left, int right){ 
        int tmpLeft = left;
        int tmpRight = right;
        int cur = arr[left];
        while (left < right){ 
            while (arr[right] >= cur && right > left) { 
                right--;
            }
            arr[left] = arr[right];
            while (arr[left] < cur && right > left) { 
                left ++;
            }
            arr[right] = arr[left];
        }
        arr[left] = cur;
        if (left - tmpLeft > 1){ 
            quickSort(arr,tmpLeft,left-1);
        }
        if (tmpRight - left > 0){ 
            quickSort(arr,left+1,tmpRight);
        }
    }

## 三、直接插入排序 ##

### 3-1：直接插入排序的解释 ###

> 我们从 1 开始遍历每一个元素（i），然后把元素 i 插入到 0-i 里面最合适的位置，这样就排好序了。

![在这里插入图片描述][2020052614415986.gif]

### 3-2：直接插入排序的代码 ###

public void insertSort(int[] arr){ 
        int tmp,j;
        for (int i = 1;i < arr.length; i++){ 
            if (arr[i] < arr[i-1]){ 
                tmp = arr[i];
                for (j = i;j > 0; j--){ 
                    if (tmp < arr[j-1]){ 
                        arr[j] = arr[j-1];
                    }else { 
                        break;
                    }
                }
                arr[j] = tmp;
            }
        }
    }

## 四、希尔排序 ##

### 4-1：希尔排序解释 ###

<table> 
 <thead> 
  <tr> 
   <th>平均时间复杂度</th> 
   <th>最好时间复杂度</th> 
   <th>最坏时间复杂度</th> 
   <th>空间复杂度</th> 
   <th>稳定性</th> 
   <th>类别</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>O(n<sup>1.3</sup>)</td> 
   <td>O(n)</td> 
   <td>O(n<sup>2</sup>)</td> 
   <td>O(1)</td> 
   <td>不稳定</td> 
   <td>交换排序</td> 
  </tr> 
 </tbody> 
</table>

> 希尔排序其实是直接插入排序的一个改进。 直接插入排序每次移动的步长都是 1 ，而希尔排序的步长从 size 开始 直到 1，这样做的使得 大的数字比较靠后，小的数字比较靠前。 当进行步长为 1 的直接插入排序的时候，就不会出现每次移动很多的情况。  
>   
> 先将整个待排序列分割成若干个子序列，对每个子序列进行直接插入排序，等到整个序列基本有序的时候，在进行一次整体的直接插入排序（也就是 步长为 1）。

![在这里插入图片描述][20200526144212598.gif]

public void shellInsert(int[] arr, int step){ 
        int tmp;
        int m;
        for (int i = 0; i < step; i++){ 
            for (int n = i + step;n < arr.length; n += step){ 
                if (arr[n] < arr[n - step]){ 
                    tmp = arr[n];
                    for (m = n-step;m >= 0; m -= step){ 
                        if (tmp < arr[m]){ 
                            arr[m + step] = arr[m];
                        }else { 
                            break;
                        }
                    }
                    arr[m+step] = tmp;
                }
            }
        }
    }
    
    public void shellSort(int[] arr){ 
        int step = arr.length / 2;
    // int step = 1;
        while (step >= 1){ 
            shellInsert(arr, step);
            step = step / 2;
        }
    }

## 五、直接选择排序 ##

### 5-1：直接选择排序解释 ###

<table> 
 <thead> 
  <tr> 
   <th>平均时间复杂度</th> 
   <th>最好时间复杂度</th> 
   <th>最坏时间复杂度</th> 
   <th>空间复杂度</th> 
   <th>稳定性</th> 
   <th>类别</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>O(n<sup>2</sup>)</td> 
   <td>O(n<sup>2</sup>)</td> 
   <td>O(n<sup>2</sup>)</td> 
   <td>O(1)</td> 
   <td>不稳定</td> 
   <td>选择排序</td> 
  </tr> 
 </tbody> 
</table>

> 每次从i - length-1中选择出 一个最小（最大）的数字，然后和 i 进行交换。

\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-i4WCqdFO-1590475243176)(![在这里插入图片描述][20200526144226315.gif]

### 5-2：直接选择排序代码 ###

public void  selectSort(int[] arr){ 
        int min_i,tmp;
        for (int i = 0;i < arr.length - 1; i++){ 
            min_i = i;
            for (int j = i+1;j < arr.length; j++){ 
                if (arr[min_i] > arr[j]){ 
                    min_i = j;
                }
            }
            tmp = arr[i];
            arr[i] = arr[min_i];
            arr[min_i] = tmp;
        }
    }

## 六、堆排序 ##

### 6-1：堆排序解释 ###

<table> 
 <thead> 
  <tr> 
   <th>平均时间复杂度</th> 
   <th>最好时间复杂度</th> 
   <th>最坏时间复杂度</th> 
   <th>空间复杂度</th> 
   <th>稳定性</th> 
   <th>类别</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>O(nlog<sub>2</sub>n)</td> 
   <td>O(nlog<sub>2</sub>n)</td> 
   <td>O(nlog<sub>2</sub>n)</td> 
   <td>O(1)</td> 
   <td>不稳定</td> 
   <td>选择排序</td> 
  </tr> 
 </tbody> 
</table>

> 把待排序列变成最大堆（最小堆），然后取出对顶元素。重复以上操作，直到排序结束。  
> 最大堆你可以把它看成二叉树，根元素，大于左右节点。

![在这里插入图片描述][20200526144236995.gif]

### 6-2：堆排序代码 ###

//当列表第一个是以下标0开始，结点下标为i,左孩子则为2*i+1,右孩子下标则为2*i+2,若下标以1开始，左孩子则为2*i,右孩子则为2*i+１
    public static void heapAdjust(int a[], int s, int m){ 
        int key = a[s];
        for(int j = 2*s + 1; j <= m; j = 2*j + 1 ){ 
            // 找到左节点和右节点中小的节点
            if(j < m && a[j] <= a[j+1] ) { 
                ++j;
            }
            // 如果当前值比左右节点最小值还小就不用管了
            if( a[j] <= key ){ 
                break;
            }
            a[s] = a[j];
            s = j;
        }
        a[s] = key;
    }
    public static void heap_sort(int a[], int size){ 
        //初始建堆,从最后一个非叶子节点开始
        for(int i = size/2-1; i >= 0; --i){ 
            heapAdjust(a, i, size-1);
        }
        //取堆顶，并且调整
        int tmp;
        for(int i = size-1; i > 0 ; --i){ 
            tmp = a[0];
            a[0] = a[i];
            a[i] = tmp;
            heapAdjust(a, 0, i-1);
        }
    }

## 七、归并排序 ##

### 7-1：归并排序的解释 ###

<table> 
 <thead> 
  <tr> 
   <th>平均时间复杂度</th> 
   <th>最好时间复杂度</th> 
   <th>最坏时间复杂度</th> 
   <th>空间复杂度</th> 
   <th>稳定性</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>O(nlog<sub>2</sub>n)</td> 
   <td>O(nlog<sub>2</sub>n)</td> 
   <td>O(nlog<sub>2</sub>n)</td> 
   <td>O(n)</td> 
   <td>稳定</td> 
  </tr> 
 </tbody> 
</table>

> 把序列尽可能的等分，然后两半分别排序。排序好后再合并排序

![在这里插入图片描述][20200526144247594.gif]

### 7-2：归并排序代码 ###

/** * 每个部分进行排序 */
    public void sort(int[] arr,int i,int mid,int j){ 
        int[] brr = new int[j-i+1];
        int start_one = i;
        int start_two = mid+1;
        int cur = 0;
        while (start_one <= mid && start_two <= j){ 
            brr[cur ++] = arr[start_one] < arr[start_two] ? arr[start_one ++] : arr[start_two ++];
        }
        while (start_one <= mid){ 
            brr[cur ++] = arr[start_one++];
        }
        while (start_two <= j){ 
            brr[cur ++] = arr[start_two++];
        }
        for (int k = 0;k < cur; k++){ 
            arr[i ++] = brr[k];
        }
    }
    
    /** * 拆分成一个个部分 */
    public void mergeSort(int[] arr,int i,int j){ 
        if (i >= j) return;
        int mid = (i + j) / 2;
        mergeSort(arr, i, mid);
        mergeSort(arr,mid + 1, j);
        sort(arr, i,mid,j);
    }

## 八、基数排序 ##

### 8-1：基数排序的解释 ###

<table> 
 <thead> 
  <tr> 
   <th>平均时间复杂度</th> 
   <th>最好时间复杂度</th> 
   <th>最坏时间复杂度</th> 
   <th>空间复杂度</th> 
   <th>稳定性</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>O(d(r+n))</td> 
   <td>O(d(n+rd))</td> 
   <td>O(nlog<sub>2</sub>n)</td> 
   <td>O(n)</td> 
   <td>稳定</td> 
  </tr> 
 </tbody> 
</table>

> 基数排序要根据具体的序列规则来做，这里以最简单的十位数为例，作图。  
> 先以个位数进行排序，然后再以10位数进行排序。回收的结果就是排序好的结果。

![在这里插入图片描述][20200526144258965.gif]

### 8-2：基数排序代码 ###

因为基数排序和具体的序列有关，这里以最简单的个位数为例，方便你阅读代码。

public static void radixSort(int[] arr){ 
        // 创建0-9的桶
        List<List<Integer>> lists = new ArrayList<>();
        for (int i = 0;i < 10; i++){ 
            lists.add(new ArrayList<>());
        }
        // 按照顺序把数字装入桶中
        for (int j = 0;j < arr.length; j++){ 
            lists.get(arr[j]).add(arr[j]);
        }
        // 按照顺序回收桶中的数据
        int cur = 0;
        for (List<Integer> item : lists){ 
            for (Integer i : item){ 
                arr[cur ++] = i;
            }
        }
    }

## 测试代码 ##

> 你可以使用下面的工具类，对你写的排序方法进行测试。

/** * 测试排序规则 * 1、测试100次，每次随机出现0-100的数字 * 2、arr 使用系统的排序， brr我们自己的排序， crr 不排序 * 3、对比arr 和 brr看是否相同，如不相同就打印 arr、brr 、crr * 4、你每次只需要替换下面注释地 * * @author 小道仙 * @date 2020年5月23日 */
    public static boolean testSort(){ 
        int arrayLenght = 100;
        int[] arr = new int[arrayLenght];
        int[] brr = new int[arrayLenght];
        int[] crr = new int[arrayLenght];
        int tmp,cur;
        for (int i = 0;i < 10000; i++){ 
            cur = 0;
            for (int j = 0; j < arrayLenght; j++){ 
                tmp = (int)(Math.random()*100);
                arr[cur] = tmp;
                crr[cur] = tmp;
                brr[cur ++] = tmp;
            }
            Arrays.sort(arr);
           
            try { 
                // 每次测试替换掉下面的这个排序方法
                // heap_sort(brr, brr.length);
            }catch (Exception e){ 
                e.printStackTrace();
            }
            for (int k = 0;k < cur; k++){ 
                if (arr[k] != brr[k]){ 
                    print(arr,brr,crr);
                    return false;
                }
            }
        }
        return true;
    }
    
    
    private static void print(int[] arr,int[] brr,int[] crr){ 
        System.out.print("arr : ");
        for (int i = 0;i < arr.length; i++){ 
            System.out.print(arr[i] + " ");
        }
    
        System.out.println();
        System.out.print("brr : ");
        for (int i = 0;i < brr.length; i++){ 
            System.out.print(brr[i] + " ");
        }
    
        System.out.println();
        System.out.print("crr : ");
        for (int i = 0;i < crr.length; i++){ 
            System.out.print(crr[i] + " ");
        }
        System.out.println();
        System.out.println();
    }

**关注我吧，一个喜欢胡思乱想的程序员。**

![在这里插入图片描述][20200526144358874.jpg]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RvbXdpbGRib2Fy_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200526144117520.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RvbXdpbGRib2Fy,size_16,color_FFFFFF,t_70
[20200526144133752.gif]: https://img-blog.csdnimg.cn/20200526144133752.gif
[2020052614414658.gif]: https://img-blog.csdnimg.cn/2020052614414658.gif
[2020052614415986.gif]: https://img-blog.csdnimg.cn/2020052614415986.gif
[20200526144212598.gif]: https://img-blog.csdnimg.cn/20200526144212598.gif
[20200526144226315.gif]: https://img-blog.csdnimg.cn/20200526144226315.gif
[20200526144236995.gif]: https://img-blog.csdnimg.cn/20200526144236995.gif
[20200526144247594.gif]: https://img-blog.csdnimg.cn/20200526144247594.gif
[20200526144258965.gif]: https://img-blog.csdnimg.cn/20200526144258965.gif
[20200526144358874.jpg]: https://img-blog.csdnimg.cn/20200526144358874.jpg