八大排序老忘？视图结合高效写出代码！

麦洛

发布于 2021-07-05 18:33:32

2380

发布于 2021-07-05 18:33:32

文章被收录于专栏：麦洛的历劫之路麦洛的历劫之路

相信很多友友在笔试或者面试的前，如果遇到排序的问题，心中就在想，就是那样那样。可是，一到面对的时候，总是心里一咯噔，沃擦，我怎么说不上来了？本文我会把自己如何快速学习排序的过程分享出来。

文章目录

八大排序老忘？视图结合高效写出代码！
1. 选择排序（Selection Sort）
- 1.1 选择排序是什么？
- 1.2 选择排序基本思想
- 1.3 算法描述
2、插入排序（Insertion Sort）
- 2.1 插入排序是什么？
- 2.2 插入排序的基本思想
- 2.3 算法描述
3、冒泡排序（Bubble Sort）
- 3.1 什么是冒泡排序？
- 3.2.冒泡排序的基本思想
- 3.2. 算法描述
4、快速排序（Quick Sort）
- 4.1 什么是快速排序（快排）？
- 4.2 快速排序基本思想
- 4.3 算法实现
总结

八大排序老忘？视图结合高效写出代码（下）！

1. 选择排序（Selection Sort）

1.1 选择排序是什么？

我们先来看一看选择排序的动态演示图：

1.2 选择排序基本思想

 选择排序的基本思想是选择+排序
  在未排序序列中找到最小（大）元素，存放到未排序序列的起始位置。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种

1.3 算法描述

根据上图可以观察得： 1.从待排序的序列中，找到最小的元素。 2.如果待排序列第一个元素不是最小的元素，那么就开始往后遍历，找到最小元素，和第一个元素交换位置； 3.从余下的待排序列中（N-1），执行1，2步骤，重复操作，直到结束。代码实现：

import java.util.Arrays;

public class Demo {
    //选择排序
    /**
     *1.从待排序序列中，找到关键字最小的元素；
     * 2.如果最小元素不是待排序序列的第一个元素，将其和第二个元素交换；
     * 3.从余下的N-1个元素中，找出关建字最小的元素，重复1.2步骤，直到排序排序结束
     * 当增量因子微一时，整个序列长度为原来序列的长度；
     */

    public static void main(String[] args) {
        int[] arr  = {25,89,56,88,21,3,56,66,8,663,55};
        Selectionchose(arr);
        System.out.println("========================");
        int[] res = Selectchose1(arr);
        System.out.println(Arrays.toString(res));

    }
//展示选择的过程
    public  static  void Selectionchose(int[] arr){
        if(arr==null||arr.length==0) return;
        //开始遍历，寻找最小的元素，打印出来
        for(int i=0;i<arr.length-1;i++){
            int min = i;
            for(int j=i+1;j<arr.length;j++){
                if(arr[j]<arr[min]){
                    min =j;
                }
            }
            if(min!=i){
                int temp = arr[min];
                arr[min] = arr[i];
                arr[i] = temp;
                System.out.println(Arrays.toString(arr));
            }
        }
    }
//直接返回最终结果
    public static  int[] Selectchose1(int[] arr){
        if(arr==null||arr.length==0){
            System.out.println("序列不合法！");
            return null;
        }
        for(int i =0;i<arr.length-1;i++){
            int min = i;
            for(int j =i+1;j<arr.length;j++){
                if(arr[min]>arr[j]){
                    min =j;
                }
            }
            if(min!=i){
                int res = arr[i];
                arr[i] = arr[min];
                arr[min] = res;
            }
        }
       return arr;
    }
}

在这里插入图片描述

2、插入排序（Insertion Sort）

2.1 插入排序是什么？

我们来看一看插入排序的动态演示图：

2.2 插入排序的基本思想

直接插入排序的基本思想是：将数组中的所有元素依次跟前面已经排好的元素相比较；
如果当前元素的值比之前已经排好的序列中的元素依次比大小，如果比之前序列数小，就直接插入到之前序列数的前面，否则不动；

2.3 算法描述

一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

①. 从第一个元素开始，该元素可以认为已经被排序 ②. 取出下一个元素，在已经排序的元素序列中从后向前扫描 ③. 如果该元素（已排序）大于新元素，将该元素移到下一位置 ④. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置 ⑤. 将新元素插入到该位置后 ⑥. 重复步骤②~⑤

代码实现：

import java.util.Arrays;

public class Deom {
    /**
     * 插入排序
     */

    public static void main(String[] args) {
        int[] arr = {25,89,56,88,21,3,56,66,8,663,55};
        //insertionSort(arr);
        insertionSort1(arr);
    }
    //序列较少的情况下：
    public  static  void insertionSort(int[] arr){
       if(arr==null||arr.length==0) return;
       for(int i =1;i<arr.length;i++){
           int temp = arr[i]; //取出第二个元素；
           for(int j =i;j>=0;j--){
              if(j>0&&arr[j-1]>temp){//j-1为当前元素的前一个元素的下标，如果前一个数大于当前的元素，那么两个数据进行交换
                  arr[j] = arr[j-1];
                  System.out.println("inserting"+Arrays.toString(arr));
              }else{
                  arr[j]=temp;//如果大于或等于，那么保存当前数，并且进入下一次插入；
                  System.out.println("Sorting"+Arrays.toString(arr));
                  break;
              }

           }
       }
    }
//数据量比较多的时候
    public  static  void insertionSort1(int[] arr){
        if(arr.length==0||arr==null) return;
        for(int i =0;i<arr.length-1;i++){
            for(int j = i+1;j>0;j--){
                if(arr[j-1]<arr[j]){
                    break;  //如果前一个元素小于当前元素，不做处理
                }
                int temp = arr[j];  //如果前一个元素大于或等于当前元素时，交换数值，然后进入循环。
                arr[j] = arr[j-1];
                arr[j-1] = temp;
            }
        }
        System.out.println(Arrays.toString(arr));
    }
}

在这里插入图片描述

3、冒泡排序（Bubble Sort）

在这里插入图片描述

3.1 什么是冒泡排序？

如果你看见过冒泡泡，那么我们可以看见，泡泡在水下向上浮的时候，泡泡的越来越小，及就是大的下沉，小的上浮；

在这里插入图片描述

3.2.冒泡排序的基本思想

 冒泡排序（Bubble Sort）是一种简单的排序算法。它重复地走访过要排序的数列，
 一次比较两个元素，如果他们的顺序错误就把他们交换过来。
 走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
 这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

3.2. 算法描述

我们先来看一看动态演示图来加深理解；

我们可以看出，大数不断往后移动，小数往前移动。冒泡排序算法的运作如下：

①. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。 ②. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。 ③. 针对所有的元素重复以上的步骤，除了最后一个。 ④. 持续每次对越来越少的元素重复上面的步骤①~③，直到没有任何一对数字需要比较。代码实现：

import java.util.Arrays;

public class Deom {
    public static void main(String[] args) {
        int[] arr = {25,89,56,88,21,3,56,66,8,663,55};
         BubbleSort(arr);
    }
    public  static  void BubbleSort(int[] arr){
        if(arr.length==0||arr==null) return;
        for(int i =0;i<arr.length;i++){  //表示第一个元素
            for(int j = i+1;j<arr.length;j++){ //表示第二个元素
                if(arr[i]>=arr[j]){ //如果第一个元素大于等于第二个元素，那么两个元素进行交换，直到不满条件；
                    int temp = arr[i];
                    arr[i] =arr[j];
                    arr[j] = temp;
                }
            }
        }
        System.out.println(Arrays.toString(arr));
    }
}

在这里插入图片描述

4、快速排序（Quick Sort）

4.1 什么是快速排序（快排）？

 快速排序（Quicksort）是对冒泡排序的一种改进，借用了分治的思想，由C. A. R. Hoare在1962年提出。

在这里插入图片描述

4.2 快速排序基本思想

快速排序的基本思想：挖坑填数+分治法。

首先选一个轴值(pivot，也有叫基准的)，通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。 先给出其处理大量数据时的效率图：

单元排序演示：

4.3 算法实现

快速排序使用分治策略来把一个序列（list）分为两个子序列（sub-lists）。步骤为：

①. 从数列中挑出一个元素，称为”基准”（pivot）。 ②. 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。 ③. 递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。

递归到最底部时，数列的大小是零或一，也就是已经排序好了。这个算法一定会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

代码实现：（递归方法）

import java.util.Arrays;

/**
 * 用伪代码描述如下：
 *
 * ①. i = L; j = R; 将基准数挖出形成第一个坑a[i]。
 * ②．j--，由后向前找比它小的数，找到后挖出此数填前一个坑a[i]中。
 * ③．i++，由前向后找比它大的数，找到后也挖出此数填到前一个坑a[j]中。
 * ④．再重复执行②，③二步，直到i==j，将基准数填入a[i]中
 * ————————————————
 *
 */

public class Deom {
    public static void main(String[] args) {
        int[] arr = {25,89,56,88,21,3,56,66,8,663,55};
        QuickSort(arr,0,arr.length-1);//以第一个数为基准
    }
    public static void QuickSort(int[] arr ,int low,int high){
        if(arr==null||arr.length==0) return;
        if(low>=high) return;
        int left = low;
        int right = high;
        int temp = arr[left]; //确定基准值；
        while (left<right){
            while (left<right&&arr[right]>=temp){  //从后往前，找到小于或等于基准的数进行交换
                right--;
            }
            arr[left] = arr[right];

            while (left<right&&arr[left]<=temp){  //从前往后走，找到大于或等于基准的数进行交换
                left++;
            }
            arr[right] = arr[left];
        }
      arr[left]=temp; //将基准值填到坑3中
        //开始递归；
        QuickSort(arr,low,left-1);
        QuickSort(arr,left+1,high);
        System.out.println(Arrays.toString(arr));
    }
   
}

上面是递归版的快速排序：通过把基准temp插入到合适的位置来实现分治，并递归地对分治后的两个划分继续快排。那么非递归版的快排如何实现呢？因为递归的本质是栈，所以我们非递归实现的过程中，可以借助栈来保存中间变量就可以实现非递归了。在这里中间变量也就是通过QuickSort1函数划分区间之后分成左右两部分的首尾指针，只需要保存这两部分的首尾指针即可。

import java.util.Arrays;
import java.util.Stack;

/**
 * 用伪代码描述如下：
 *
 * ①. i = L; j = R; 将基准数挖出形成第一个坑a[i]。
 * ②．j--，由后向前找比它小的数，找到后挖出此数填前一个坑a[i]中。
 * ③．i++，由前向后找比它大的数，找到后也挖出此数填到前一个坑a[j]中。
 * ④．再重复执行②，③二步，直到i==j，将基准数填入a[i]中
 * ————————————————
 *
 */

public class Deom {
    public static void main(String[] args) {
        int[] arr = {25,89,56,88,21,3,56,66,8,663,55};
       // QuickSort(arr,0,arr.length-1);//以第一个数为基准、
        quickSortByStack(arr);
    }
    public static void QuickSort(int[] arr ,int low,int high){
        if(arr==null||arr.length==0) return;
        if(low>=high) return;
        int left = low;
        int right = high;
        int temp = arr[left]; //确定基准值；
        while (left<right){
            while (left<right&&arr[right]>=temp){  //从后往前，找到小于或等于基准的数进行交换
                right--;
            }
            arr[left] = arr[right];

            while (left<right&&arr[left]<=temp){  //从前往后走，找到大于或等于基准的数进行交换
                left++;
            }
            arr[right] = arr[left];
        }
      arr[left]=temp; //将基准值填到坑3中
        //开始递归；
        QuickSort(arr,low,left-1);
        QuickSort(arr,left+1,high);
        System.out.println(Arrays.toString(arr));
    }
    /**
     * 快速排序（非递归）
     *
     * ①. 从数列中挑出一个元素，称为"基准"（pivot）。
     * ②. 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
     * ③. 把分区之后两个区间的边界（low和high）压入栈保存，并循环①、②步骤
     * @param arr   待排序数组
     */
    public static void quickSortByStack(int[] arr){
        if(arr.length <= 0) return;
        Stack<Integer> stack = new Stack<Integer>();

        //初始状态的左右指针入栈
        stack.push(0);
        stack.push(arr.length - 1);
        while(!stack.isEmpty()){
            int high = stack.pop();     //出栈进行划分
            int low = stack.pop();
            int pivotIdx = QuickSort1(arr, low, high);
            //保存中间变量
            if(pivotIdx > low) {
                stack.push(low);
                stack.push(pivotIdx - 1);
            }
            if(pivotIdx < high && pivotIdx >= 0){
                stack.push(pivotIdx + 1);
                stack.push(high);
            }
        }
    }

    private static int QuickSort1(int[] arr, int low, int high){
        if(arr.length <= 0) return -1;
        if(low >= high) return -1;
        int l = low;
        int r = high;

        int pivot = arr[l];    //挖坑1：保存基准的值
        while(l < r){
            while(l < r && arr[r] >= pivot){  //坑2：从后向前找到比基准小的元素，插入到基准位置坑1中
                r--;
            }
            arr[l] = arr[r];
            while(l < r && arr[l] <= pivot){   //坑3：从前往后找到比基准大的元素，放到刚才挖的坑2中
                l++;
            }
            arr[r] = arr[l];
        }
        arr[l] = pivot;   //基准值填补到坑3中，准备分治递归快排
        System.out.println(Arrays.toString(arr));
        return l;
    }
} 
```

![在这里插入图片描述](https://img-blog.csdnimg.cn/20210517214758587.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0lMT1ZFTVlERUFS,size_16,color_FFFFFF,t_70#pic_center)  
排序是通常被认为在同数量级（O(nlog2n)）的排序方法中平均性能最好的。但若初始序列按关键码有序或基本有序时，快排序反而蜕化为冒泡排序。为改进之，通常以“三者取中法”来选取基准记录，即将排序区间的两个端点与中点三个记录关键码居中的调整为支点记录。快速排序是一个不稳定的排序方法。

[](https://blog.csdn.net/ILOVEMYDEAR/article/details/116943667)总结
=================================================================

小胡呕心沥血写了四个排序的图解，太累了，容我再过今天再详细写其他排序算法；排序的时间复杂度和稳定性我会单独写一篇文章，今天我们主要掌握算法，别忘了收藏，转发，评论偶！

 

  

本文转自 [https://blog.csdn.net/ILOVEMYDEAR/article/details/116943667](https://blog.csdn.net/ILOVEMYDEAR/article/details/116943667)，如有侵权，请联系删除。

往期推荐

聊一聊我最近使用的uniCloud是个什么玩意?

厉害了！把 HashMap 剖析的只剩渣了！

聊聊MySQL的COUNT()的性能,看看怎么最快?

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2021-05-28，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自今日Java 微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度