排序算法

2021-04-07 约 2165 字预计阅读 5 分钟次阅读

冒泡排序

冒泡排序是通过比较两个相邻元素的大小实现排序，如果前一个元素大于后一个元素，就交换这两个元素。这样就会让每一趟冒泡都能找到最大一个元素并放到最后。

以 [ 8, 1, 4, 6, 2, 3, 5, 7 ] 为例，对它进行冒泡排序：

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


public static int[] maopaoSort(int[] array){
        boolean isChanged=false;
        for(int i=0;i<array.length-1;i++){
            for(int j=0;j<array.length-1-i;j++){
                if(array[j]>array[j+1]){
                    int temp=array[j+1];
                    array[j+1]=array[j];
                    array[j]=temp;
                    isChanged=true;
                }
            }
        }
        return array;
    }

特点

稳定性：它是指对同样的数据进行排序，会不会改变它的相对位置。比如 [ 1, 3, 2, 4, 2 ] 经过排序后，两个相同的元素 2 位置会不会被交换。冒泡排序是比较相邻两个元素的大小，显然不会破坏稳定性。
空间复杂度：由于整个排序过程是在原数据上进行操作，故为 O(1);
时间复杂度：由于嵌套了 2 层循环，故为 O(n*n);

选择排序

选择排序的思想是，依次从「无序列表」中找到一个最小的元素放到「有序列表」的最后面。以 arr = [ 8, 1, 4, 6, 2, 3, 5, 4 ] 为例，排序开始时把 arr 分为有序列表 A = [ ], 无序列表 B = [ 8, 1, 4, 6, 2, 3, 5, 4 ]，依次从 B 中找出最小的元素放到 A 的最后面。这种排序也是逻辑上的分组，实际上不会创建 A 和 B，只是用下标来标记 A 和 B。

以 arr = [ 8, 1, 4, 6, 2, 3, 5, 4 ] 为例，第一次找到最小元素 1 与 8 进行交换，这时有列表 A = [1], 无序列表 B = [8, 4, 6, 2, 3, 5, 4]；第二次从 B 中找到最小元素 2，与 B 中的第一个元素进行交换，交换后 A = [1，2]，B = [4, 6, 8, 3, 5, 4]；就这样不断缩短 B，扩大 A，最终达到有序。

代码实现

方法一：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


public static int[] selectSort(int[] array){
        for(int i=0;i<array.length-1;i++){
            int index=i;

            //找出n次无序列表中的最小值和他的下标
            for(int j=i;j<array.length;j++){
                if(array[j]<array[index]) {
                    index = j;
                }
            }
           int temp=array[index];
            array[index]=array[i];
            array[i]=temp;
        }
        return array;
    }

方法二：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


public static int[] selectSort(int[] array){
        for(int i=0;i<array.length-1;i++){
            int index=i;
            int temp=999;
            //找出n次无序列表中的最小值和他的下标
            for(int j=i;j<array.length;j++){
                if(array[j]<array[index]){
                    index=j;
                }
                temp=array[index];
            }
            //把[i,index]后移一位，给有序增加空位，插入最小值
            for(int m=index;m>i;m--){
                array[m]=array[m-1];
            }
            array[i]=temp;
        }
        return array;
    }

特点

稳定性：排序过程中元素是按顺序进行遍历，相同元素相对位置不会发生变化，故稳定。
空间复杂度：在原序列进行操作，故为 O( 1 );
时间复杂度：需要 2 次循环遍历，故为 O( n * n );

插入排序

在整个排序过程如图所示，以 arr = [ 8, 1, 4, 6, 2, 3, 5, 7] 为例，它会把 arr 分成两组 A = [ 8 ] 和 B = [ 1, 4, 6, 2, 3, 5, 7] ，逐步遍历 B 中元素插入到 A 中，最终构成一个有序序列：

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


public static int[] insertSort(int[] array){
        for(int i=1;i<array.length;i++){
            int preindex=i-1;
            // 必须记录这个元素，不然会被覆盖掉
            int current=array[i];
            // 当前元素小于排序好的元素，就移动到下一个位置,从后向前找位置插入
            while(preindex>=0&&current<array[preindex]){
                array[preindex+1]=array[preindex];
                preindex--;
            }
            array[preindex+1]=current;
        }
        return array;
    }

特点

稳定性：它是从后往前遍历已排序好的序列，相同元素不会改变位置，故为稳定排序；
空间复杂度：它是在原序列进行排序，故为 O ( 1 );
时间复杂度：排序的过程中，首先要遍历所有的元素，然后在已排序序列中找到合适的位置并插入。共需要 2 层循环，故为 O ( n * n );

希尔排序

希尔排序，它是由 D.L.Shell 于1959 年提出而得名。根据它的名字很难想象算法的核心思想。[ 所以只能死记硬背了，面试官问：希尔排序的思想是什么？]。它的核心思想是把一个序列分组，对分组后的内容进行插入排序，这里的分组只是逻辑上的分组，不会重新开辟存储空间。它其实是插入排序的优化版，插入排序对基本有序的序列性能好，希尔排序利用这一特性把原序列分组，对每个分组进行排序，逐步完成排序。

以 arr = [ 8, 1, 4, 6, 2, 3, 5, 7 ] 为例，通过 floor(8/2) 来分为 4 组，8 表示数组中元素的个数。分完组后，对组内元素进行插入排序。

「利用第 1 次分组结果进行第 2 次分组」

「利用第 2 次分组结果进行最后一次分组」

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


public static int[] lshellSort(int[] array){
        //len=9
        int len=array.length;
        //floor向下取整，4，2，1
        for(int gap=(int)Math.floor(len/2);gap>0;gap=gap/2){
            //i=4;
            for (int i = gap; i < len; i++) {
                // j=0,1,2,3,4
                // [0]-[4] [1]-[5] [2]-[6] [3]-[7] [4]-[8]
                for (int j = i - gap; j >= 0 && array[j] > array[j+gap]; j-=gap) {
                    // 交换位置
                    int temp = array[j];
                    array[j] = array[gap+j];
                    array[gap+j] = temp;
                }
            }
        }
        return array;
    }

特点

稳定性：它可能会把相同元素分到不同的组中，那么两个相同的元素就有可能调换相对位置，故不稳定。
空间复杂度：由于整个排序过程是在原数据上进行操作，故为 O(1);
时间复杂度：希尔排序的时间复杂度与增量序列的选取有关，例如希尔增量时间复杂度为O(n²)，而Hibbard增量的希尔排序的时间复杂度为O(log n的3/2)，希尔排序时间复杂度的下界是n*log2n

快速排序

快速排序的核心思想是对待排序序列通过一个「支点」（支点就是序列中的一个元素，别把它想的太高大上）进行拆分，使得左边的数据小于支点，右边的数据大于支点。然后把左边和右边再做一次递归，直到递归结束。支点的选择也是一门大学问，我们以（左边index + 右边index）/ 2 来选择支点。

以 arr = [ 8, 1, 4, 6, 2, 3, 5, 7 ] 为例，选择一个支点, index= (L+R)/2 = (0+7)/2=3, 支点的值 pivot = arr[index] = arr[3] = 6，接下来需要把 arr 中小于 6 的移到左边，大于 6 的移到右边。

快速排序使用一个高效的方法做数据拆分。

用一个指向左边的游标 i，和指向右边的游标 j，逐渐移动这两个游标，直到找到 arr[i] > 6 和 arr[j] < 6, 停止移动游标，交换 arr[i] 和 arr[j]，交换完后 i++，j–（对下一个元素进行比较），直到 i>=j，停止移动。

图中的 L，R 是指快速排序开始时序列的起始和结束索引，在一趟快速排序中，它们的值不会发生改变，直到下一趟排序时才会改变。

一趟快速排序完成后，分别对小于6和大于等于6的部分进行快速排序，递归就好了。对 [ 5, 1, 4, 3, 2 ] 进行一趟快速排序。

目录

排序算法

冒泡排序

代码实现

特点

选择排序

代码实现

特点

插入排序

代码实现

特点

希尔排序

代码实现

特点

快速排序

代码实现

特点

排序

代码实现

特点

排序

代码实现

特点

排序

代码实现

特点

排序

代码实现

特点

排序

代码实现

特点

排序

代码实现

特点