排序第三节——交换排序（冒泡排序+快速排序+快排的优化）（5个视频讲解）

2.3 交换排序

基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

2.3.1冒泡排序 O(N^2)（稳定）

*** 视频讲解

【冒泡排序的特性总结】

1. 冒泡排序是一种非常容易理解的排序
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：稳定

模板

    /**
     * 冒泡排序
     * 时间复杂度：O(N^2)
     *     针对优化后的代码，时间复杂度在有序的情况下：
     * 			O(n)
     * 空间复杂度：O(1)
     * 稳定性：稳定 的排序
     * 插入
     * @param array
     */
    public static void bubbleSort(int[] array) {
        for (int i = 0; i < array.length-1; i++) {
            boolean flg = false;
            for (int j = 0; j < array.length-1-i; j++) {
                if(array[j] > array[j+1]) {
                    swap(array,j,j+1);
                    flg = true;
                }
            }
            if(!flg) {
                break;
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

2.3.2 快速排序 O（N * logN）（稳定）

模板

    // 假设按照升序对array数组中[left, right)区间中的元素进行排序
    void QuickSort(int[] array, int left, int right) {
        if(right - left <= 1)
            return;

        // 按照基准值对array数组的 [left, right)区间中的元素进行划分
        int div = partion(array, left, right);

        // 划分成功后以div为边界形成了左右两部分 [left, div) 和 [div+1, right)
        // 递归排[left, div)
        QuickSort(array, left, div);

        // 递归排[div+1, right)
        QuickSort(array, div+1, right);
    }
        private static int partitionHoare(int[] array,int start,int end) {
        int i = start;//事先存储好start下标
        int key = array[start];
        while (start < end) {
            //为啥取等号？ 不然就死循环了
            while (start < end && array[end] >= key) {
                end--;
            }
            while (start < end && array[start] <= key) {
                start++;
            }
            swap(array,start,end);
        }
        swap(array,start,i);
        return start;
    }
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

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

    // 假设按照升序对array数组中[left, right)区间中的元素进行排序
    void QuickSort(int[] array, int left, int right) {
        if(right - left <= 1)
            return;

        // 按照基准值对array数组的 [left, right)区间中的元素进行划分
        int div = partion(array, left, right);

        // 划分成功后以div为边界形成了左右两部分 [left, div) 和 [div+1, right)
        // 递归排[left, div)
        QuickSort(array, left, div);

        // 递归排[div+1, right)
        QuickSort(array, div+1, right);
    }
    private static int partitionHoare(int[] array,int start,int end) {
        int i = start;//事先存储好start下标
        int key = array[start];
        while (start < end) {
            //为啥取等号？ 不然就死循环了
            while (start < end && array[end] >= key) {
                end--;
            }
            while (start < end && array[start] <= key) {
                start++;
            }
            swap(array,start,end);
        }
        swap(array,start,i);
        return start;
    }
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

上述为快速排序递归实现的主框架，发现与二叉树前序遍历规则非常像，同学们在写递归框架时可想想二叉树前序遍历规则即可快速写出来，后序只需分析如何按照基准值来对区间中数据进行划分的方式即可。

区间按照基准值划分为左右两半部分的常见方式

1. Hoare版（右，左两两交换）

***视频讲解

1. Hoare版
   

2. 挖坑法

*** 视频讲解

3. 前后指针

写法一：
写法二：

2.3.2 快速排序优化

***视频讲解

1. 三数取中法选key

//三数取中：解决递归深度问题 基本上 有了三数取中  你的待排序序列 基本上每次都是二分N*logn
int index = midNumIndex(array,left,right);
swap(array,left,index);

    /**
     * 三数取中
     * @param array
     * @param left
     * @param right
     * @return
     */
    private static int midNumIndex(int[] array,int left,int right) {
        int mid = (left+right) / 2 ;
        // 3  <  9
        if(array[left] < array[right]) {
            if(array[mid] < array[left]) {
                return left;
            }else if(array[mid] > array[right]) {
                return right;
            }else {
                return mid;
            }
        }else {
            //9 > 3
            if(array[mid] < array[right]) {
                return right;
            }else if(array[mid] > array[left]){
                return left;
            }else {
                return mid;
            }
        }
    }
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

2. 当区间跨度小于8的时候，就用插入排序

if(right - left + 1 <= 7) {
    //使用直接插入排序
    insertSort2(array,left,right);
    return;
}
1
2
3
4
5

    public static void insertSort2(int[] array,int start,int end) {
    //此函数是插入排序
        for (int i = start+1; i <= end; i++) {
            int tmp = array[i];
            int j = i-1;
            for(;j >= start;j--) {
                //加上等号 就是不稳定
                if(array[j] > tmp) {
                    array[j+1] = array[j];
                }else {
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }

    private static void quick(int[] array,int left,int right) {
        //这里代表 只要一个节点了 大于号：有可能没有子树  有序  逆序
        if(left >= right) {
            return;
        }

        //小区间使用直接插入排序： 主要 优化了递归的深度
        if(right - left + 1 <= 7) {
            //使用直接插入排序
            insertSort2(array,left,right);
            return;
        }

        //三数取中：解决递归深度问题 基本上 有了三数取中  你的待排序序列 基本上每次都是二分N*logn
        int index = midNumIndex(array,left,right);
        swap(array,left,index);

        int pivot = partitionHoare(array,left,right);

        quick(array,left,pivot-1);
        quick(array,pivot+1,right);
    }

    /**
     * 时间复杂度：O(N*logN) 【理想-》每次都是均分待排序序列】
     *          最慢：O(n^2) 数据有序或者逆序
     * 空间复杂度：
     *      最好：O(logN)
     *      最坏：O(N)  当N 足够大的时候 ，递归的深度就大
     * 稳定性：不稳定
     * @param array
     */
    public static void quickSort1(int[] array) {
        quick(array,0,array.length-1);
    }

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

2.3.3 快速排序非递归

***视频讲解

    /**
     * 非递归实现 快速排序
     * @param array
     */
    public static void quickSort(int[] array) {
        Stack<Integer> stack = new Stack<>();
        int left = 0;
        int right = array.length-1;
        //三数取中：解决递归深度问题 基本上 有了三数取中  你的待排序序列 基本上每次都是二分N*logn
        int index = midNumIndex(array,left,right);
        swap(array,left,index);
        int pivot = partitionHole(array,left,right);
        if(pivot > left+1) {
            stack.push(left);
            stack.push(pivot - 1);
        }

        if(pivot < right-1) {
            stack.push(pivot + 1);
            stack.push(right);
        }

        while (!stack.empty()) {
            right = stack.pop();
            left = stack.pop();
            index = midNumIndex(array,left,right);
            swap(array,left,index);
            pivot = partition(array,left,right);
            if(pivot > left+1) {
                stack.push(left);
                stack.push(pivot - 1);
            }
            if(pivot < right-1) {
                stack.push(pivot + 1);
                stack.push(right);
            }
        }
    }

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

2.3.4 快速排序总结