高级排序

发表于 | 分类于 |

高级排序

之前的简单排序，包括冒泡排序、选择排序、插入排序，并且对他们在最坏情况下的时间复杂度做了分析，发现都是$O(N^2)$，复杂度为平方阶的会随着输入规模的增大，时间成本急剧上升，所以这些基本排序方法不能处理更大规模的问题，接下来将会使用一些高级的排序算法，争取降低算法的时间复杂度最高阶次幂。

希尔排序

希尔排序是插入排序的一种，又称“缩小增量排序”，是插入排序算法的一种更高效的改进版本。

需求：

  • 排序前：{9，1，2，5，7，4，8，6，3，5}
  • 排序后：{1，2，3，4，5，5，6，7，8，9}

排序原理：

  • 选择一个增量h，按照增长量h作为数据分组的依据，对数据进行分组；
  • 对分好组的每一组数据完成插入排序；
  • 减小增长量，最小减为1，重复第二步操作。
初始 {9，1，2，5，7，4，8，6，3，5}
h=5 {4，1，2，3，5，9，8，6，5，7}
h=2 {2，1，4，3，5，6，5，7，8，9}
h=1 {1，2，3，4，5，5，6，7，8，9}

增长量h的确定：

1
2
3
4
5
6
7
int h = 1;
while(h < 数组长度/2){
    h = 2*h + 1;
}
//循环结束后就可以确定h的最大值
//h的减小规则为：
h = h / 2;

希尔排序的API设计：

类名 Shell
构造方法 Shell()
成员方法 public static void sort(Comparable[] a)
private static boolean greater(Comparable m, Comparable w)
private static void exch(Comparable[] a, int i, int j)

希尔排序的代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public class Shell{
    public static void sort(Comparable[] a){
        //根据数组a的长度，确定增长量h的初始值；
        int h = 1;
        while(h < (a.length / 2)){
            h = 2 * h + 1;
        }
        //希尔排序
        while(h >= 1){
            //找到待插入元素
            for(int i = h; i < a.length; i++){
                for(int j = i; j >= h; j-=h){
                    if(greater(a[j-h],a[j])){
                        exch(a,j-h,j);
                    }else{
                        break;
                    }
                }
            }
        }
        h = h / 2;
    }
    
    private static boolean greater(Comparable m, Comparable w){
        return m.compareTo(w) > 0;
    }
    
    private static void exch(Comparable[] a, int i, int j){
        Comparable temp;
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}
1
2
3
4
5
6
7
public class ShellTest{
    public static void main(String[] args){
        Integer[] arr = {9,1,2,5,7,4,8,6,3,5};
        Shell.sort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

希尔排序的时间复杂度分析：

在希尔排序中，增长量h并没有固定的规则，有很多论文研究了各种不同的递增序列，但都无法证明某个序列是最好的，对于希尔排序的时间复杂度分析，在这里不做分析了。

我们可以使用事后分析法对希尔排序和插入排序做性能比较。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public class SortCompare{
    //调用不同的测试方法，完成测试
    public static void main(String[] args) throws Exception{
        //创建一个ArrayList集合，保存读取出来的数据
        ArrayList<Integer> list = new ArrayList<>();
        //创建缓存读取流BufferedReader，读取数据，并存储到ArrayList中
        BufferedReader reader = new BufferedReader(new InputStreamReader(SortCompare.class.getclassLoader().getResourceAsStream("reverse_arr.test")));
        String line = null;
        while((line = reader.readLine()) != null){
            //line是字符串
           	//把line转换成Integer，存储到集合中
            int i = Integer.parseInt(line);
            list.add(i);
        }
        //关闭流
        reader.close();
        //把ArrayList集合转换成数据
        Integer[] a = new Integer[list.size()];
        list.toArray(a);
        
        //调用测试代码
        testInsertion(a);
        testShell(a);
    }
    
    public static void testShell(Integer[] a){
        //获取执行之间的时间
        long start = System.currentTimeMillis();
        Shell.sort(a);
        long end = System.currentTimeMillis();
        System.out.println("希尔排序执行的时间为"+ (end -start) + "ms!");
    }
    
    public static void testInsertion(Integer[] a){
        long start = System.currentTimeMillis();
        Insertion.sort(a);
        long end = System.currentTimeMillis();
        System.out.println("插入排序执行的时间为"+ (end -start) + "ms!");
    }
}

归并排序

递归

定义：定义方法时，在方法内部调用方法本身，称之为递归。

1
2
3
4
public void show(){
    System.out.println("aaaa");
    show();
}

作用：

它通常把一个大型复杂的问题，层层转换为一个与原问题相似的，规模较小的问题来求解。递归策略只需要少量的程序就可以描述出解题过程所需要的多次重复计算，大大的减少了程序的代码量。

注意事项：

在递归调用中，不能无限制的调用自己，必须要有边界条件，能够让递归结束，因为每一次递归调用都会在栈内存开辟新的空间，重新执行方法，如果递归的层级太深，很容易造成占内存溢出。

需求：

请定义一个方法，使用递归完成求$N$的阶乘。

1
2
3
4
5
6
7
8
9
10
11
public class Test{
    public static void main(String[] args){
        int result = factorial(5);
        System.out.println(result);
    }
    
    public static int factorial(int n){
        if(n == 1) return 1;
        return n * factorial(n - 1);
    }
}

归并排序

归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法的一个非常典型的应用。将已有的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

需求：

  • 排序前：{8，4，5，7，1，3，6，2}
  • 排序后：{1，2，3，4，5，6，7，8}

排序原理：

  • 1.尽可能的一组数据拆分成两个元素相等的子组，并对每一个子组继续拆分，直到拆分后的每个子组的元素个数1为止；
  • 2.将相邻的两个子组进行合并成一个有序的大组；
  • 不断重复步骤2，直到最终只有一个组为止。

归并排序的API设计：

类名 Merge
构造方法 Merge()
成员方法 public static void sort(Comparable[] a)
private static void sort(Comparable[] a, int lo, int hi)
private static void merge(Comparable[] a, int lo, int mid, int hi)
private static boolean less(Comparable v, Comparable w)
private static void exch(Comparable[] a, int i, int j)
成员变量 private static Comparable[] assist

归并排序的代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
public class Merge{
    private static Comparable[] assist;
    
    public static void sort(Comparable[] a){
        //初始化辅助数组assist
        assist = new Comparable[a.length];
        //定义一个lo变量和hi变量，分别记录数组中最小的索引和最大的索引
        int lo = 0, hi = a.length - 1;
        //调用sort重载方法完成数组a中从索引lo到hi的元素排序
        sort(a,lo,hi);
    }
    
    private static void sort(Comparable[] a, int lo, int hi){
        //安全性校验
        if(hi <= lo) return;
        //对lo到hi中的数据分两个组
        int mid = lo + (hi - lo) / 2;
        //分别对每一组数据进行排序
        sort(a,lo,mid);
        sort(a,mid+1,hi);
        //再把两个组中的数据进行归并
        merge(a,lo,mid,hi);
    }
    
    private static void merge(Comparable[] a, int lo ,int mid, int hi){
        //定义三个指针
        int p1 = lo, p2 = mid + 1, i = lo;
        //遍历，移动p1指针和p2指针，比较对应索引处的值，找出小的那个，放到辅助数组的对应索引处
        while(p1 <= mid && p2 <= hi){
            if(less(a[p1],a[p2])){
                assist[i++] = a[p1++];
            }else{
                assist[i++] = a[p2++];
            }
        }
        //遍历，如果p1指针没有走完，那么顺序移动p1指针，把对应的元素放到辅助数组的对应索引处
        while(p1 <= mid){
            assist[i++] = a[p1++];
        }
        //同理p2指针同样
        while(p2 <= hi){
            assist[i++] = a[p2++];
        }
        //把辅助数组中的元素拷贝到原数组中
        for(int index = lo; index <= hi; index++){
            a[index] = assist[index];
        }
    }
    
    private static boolean less(Comparable v, Comparable w){
        return v.compareTo(w) < 0;
    }
    
    private static void exch(Comparable[] a, int i, int j){
        Comparable temp;
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

归并排序时间复杂度分析：

归并排序是分治思想的最典型的例子，上面的算法中，对$a[lo…hi]$进行排序，先将它分为$a[lo…mid]和a[mid+1…hi]$两部分，分别通过递归调用将他们单独排序，最后将有序的子数组归并为最终的排序结果。该递归的出口在于如果一个数组不能再被分为两个子数组，那么就会执行merge进行归并，在归并的时候判断元素的大小进行排序。

用树状图来描述归并，如果一个数组有8个元素，那么它将每次除以2找最小的子数组，共拆$log8$次，值为3，所以树共有三层，那么自顶向下第$k$层有$2^k$个子数组，每个数组的长度为$2^{3-k}$，归并最多需要$2^{3-k}$次比较。因此每层的比较次数为$2^k2^{3-k} = 2^3$，那么3层总共为$32^3$。

假设元素的个数为$n$，那么使用归并排序拆分的次数为$log_2(n)$，所以共$log_2(n)$层，归并排序的时间复杂度为：$O(nlogn)$。

归并排序的缺点：

需要申请额外的数组空间，导致空间复杂度提升，是典型的以空间换时间的造作。

快速排序

快速排序是对冒泡排序的一种改进。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两个部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

需求：

  • 排序前：{6，1，2，7，9，3，4，5，8}
  • 排序后：{1，2，3，4，5，6，7，8，9}

排序原理：

  • 1.首先设定一个分界值，通过该分界值将数组分成左右两个部分;
  • 2.将大于或等于分界值的数据放到数组右边，小于分界值的数据放到数组的左边。此时左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值；
  • 3.然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
  • 4.重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好后，再递归排好右侧部分的顺序。当左侧和右侧两个部分的数据排完序后，整个数组的排序也就完成了。

快速排序API设计：

类名 Quick
构造方法 Quick()
成员方法 public static void sort(Comparable[] a)
private static void sort(Comparable[] a, int lo, int hi)
public static int partition(Comparable[] a, int lo, int hi)
private static boolean less(Comparable v, Comparable w)
private static void exch(Comparable[] a, int i ,int j)

切分原理：

  • 找一个基准值，用两个指针分别指向数组的头部和尾部；
  • 先从尾部向头部开始搜索一个比基准值小的元素，搜索到停止，并记录指针的位置；
  • 再从头部向尾部开始搜索一个比基准值大的元素，搜索到即停止，并记录指针的位置；
  • 交换当前左边指针位置和右边指针位置的元素；
  • 重复步骤2，3，4直到左边指针的值大于右边指针的值停止。

快速排序的代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
public class Quick{
    public static void sort(Comparable[] a){
        int lo = 0, hi = a.length - 1;
        sort(a,lo,hi);
    }
    
    private static void sort(Comparable[] a, int lo, int hi){
        //安全性校验
        if(hi <= lo) return;
        //需要对数组中lo索引到hi索引处的元素进行分组：左子组和右子组
        int partition = partition(a,lo,hi);//返回的是分组的分界值所在的索引
        //让左子组有序
        sort(a,lo,partition - 1);
        //让右子组有序
        sort(a,partition + 1,hi);
    }
    
    public static int partition(Comparable[] a, int lo, int hi){
        //确定分界值
        Comparable key = a[lo];
        //定义两个指针：分别指向待切分元素的最小索引处和最大索引处的下一个位置
        int left = lo, right = hi + 1;
        //切分
        while(true){
            //先从右向左扫描，移动right指针，找到一个比分界值小的元素，停止
            while(less(key,a[--right])){
                if(right == lo){
                    break;
                }
            }
            //再从左往右扫描，移动left指针，找到一个比分界值大的元素，停止
            while(less(a[++left],key)){
                if(left == hi){
                    break;
                }
            }
            //判断left》=right，如果是，结束循环；如果不是则交换元素
            if(left >= right){
                break;
            }else{
                exch(a,left,right)
            }
        }
        exch(a,lo,right);//交换分界值
        return right;
    }
    
    private static boolean less(Comparable v, Comparable w){
        return v.compareTo(w) < 0;
    }
    
    private static void exch(Comparable[] a, int i, int j){
        Comparable temp;
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

快速排序和归并排序的区别：

快速排序是另一种分治的排序算法，它将一个数组分成两个子数组，将两部分独立的排序。快速排序和归并排序是互补的：归并排序将数组分成两个子数组分别排序，并将有序的子数组归并从而将整个数组排序，而快速排序的方式则是当两个数组都是有序时，整个数组中自然就有序了。在归并排序中，一个数组被等分为两半，归并调用发生在处理整个数组之前，在快速排序中，切分数组的位置取决于数组的内容，递归调用发生在处理整个数组之后。

快速排序时间复杂度分析：

快速排序的一次切分从两头开始交替搜索，直到left和right重合，因此，一次切分算法的时间复杂度为$O(n)$，但整个快速排序的时间复杂度和切分的次数相关。

最优情况：每一次切分选择的基准数字刚好使将当前序列等分。其时间复杂度为$O(nlogn)$。

最坏情况：每一次切分选择的基准数字是当前序列中最大数或者最小数，这使得每次切分都会有一个子组，那么总共切分n次，所以最坏情况下其时间复杂度为$O(n^2)$。

平均情况：每一次切分选择的基准数字不是最大值和最小值，也不是中值。其时间复杂度为$O(nlogn)$。

排序的稳定性

稳定性的定义：

数组$arr$中有若干元素，其中A元素和B元素相等，并且A元素在B元素前面，如果使用某种排序算法后，能够保证A元素依然在B元素的前面，可以说这个算法是稳定的。

稳定性的意义：

如果一组数据只需要一次排序，则稳定性一般没有意义，如果一组数据需要多次排序，稳定性是有意义的。例如要排序的内容是一组商品对象，第一次排序按照价格由低到高排序，第二次排序按照销量由高到低排序，如果第二次排序使用稳定性算法，就可以使得相同销量的对象依旧保持着价格高低的顺序展现，只有销量不同的对象才需要重新排序。这样既可以保持第一次排序的原有意义，而且可以减少系统开销。

常见排序算法的稳定性：

  • 冒泡排序：只有当$arr[i] > arr[i + 1]$的时候，才会交换元素位置，而相等的时候不会交换位置，所以冒泡排序是一种稳定排序算法。
  • 选择排序：选择排序是给每一个位置选择当前元素最小的，例如有数据为：$5(1),8,5(2),2,9$，第一遍选择的最小元素为2，所以5(1)会和2进行位置交换，此时5(1)到了5(2)后面，破坏了稳定性，所以选择排序算法是一种不稳定的排序算法。
  • 插入排序：比较是从有序序列的末尾开始，也就是想要插入的元素和已经存在的最大者开始比起，如果比大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的，那么把要插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好后的顺序，所以插入排序是稳定的。
  • 希尔排序：希尔排序是按照不同步长对元素进行插入排序，虽然一次插入排序是稳定的，不会改变相同元素的相对位置，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以希尔排序是不稳定的。
  • 归并排序：归并排序在归并过程中，只有$arr[i] < arr[i+1]$的时候才会交换位置，如果两个元素相等则不会交换位置，所以它并不会破坏稳定性，归并排序是稳定的。
  • 快速排序：快速排序需要一个基准值，在基准值的右侧找一个比基准值小的元素，在基准值左侧找一个比基准值大的元素，然后交换这两个元素，此时会破坏稳定性，所以快速排序是一种不稳定的算法。
Donate comment here