快速排序

发表于 | 分类于 ，
字数统计: | 阅读时长 ≈

快速排序

挖坑填数+分治法

快排的思想就是:

  • 头尾指针,挖坑填数,确定一个元素,它的左边元素都比它大,右边元素都比它小
  • 递归,保证每一个子列表都满足它的左边元素都比它大,右边元素都比它小,这样就是有序的

为什么要用分治法?

根源是:一次挖坑排序,只能确保

https://blog.csdn.net/MoreWindows/article/details/6684558

可以使用分治的保障是?

每次会返回一个middle值,这个值,左边的都比他小,右边的都比他大

这样才能保证调整到最后整个数组有序

挖坑:
不需要担心数据被覆盖,因为数据都已经被保存了.

对挖坑填数进行总结

1．i =L; j = R; 将基准数挖出形成第一个坑a[i]。

2．j–由后向前找比它小的数，找到后挖出此数填前一个坑a[i]中。

3．i++由前向后找比它大的数，找到后也挖出此数填到前一个坑a[j]中。

4．再重复执行2，3二步，直到i==j，将基准数填入a[i]中。

递归实现:

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
public class QuickSort {
    private static void quickSort(int[] a, int low, int high) {
        /**
         * void: 没有返回值是因为操作数组,直接交换值
         * low,high: 是为了递归
         */
        // 递归的结束条件
        if (low >= high) {
            return;
        }
        int i, j, tmp;
        // 保留low,high为了后面的递归
        i = low;
        j = high;
        // 挖坑
        tmp = a[low];
        while (i < j) {
            while (i < j && a[j] >= tmp) {
                j--;
            }
            if (i < j) {
                a[i++] = a[j];
            }
            while (i < j && a[i] < tmp) {
                i++;
            }
            if (i < j) {
                a[j--] = a[i];
            }
        }
        // 此时i=j
        a[i] = tmp;
        quickSort(a, low, i - 1);
        quickSort(a, i + 1, high);
    }

    public static void main(String[] args) {

        int[] a = {49, 38, 65, 97, 76, 13, 27, 49};
        System.out.println(Arrays.toString(a));
        quickSort(a, 0, a.length - 1);
        System.out.println(Arrays.toString(a));

    }
}

将中间一部分抽出来,可以看到就是一个典型的递归

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
public class QuickSort {
    private static void quickSort(int[] a, int low, int high) {
        if (low >= high) {
            return;
        }
        int i = adjustArray(a, low, high);
        quickSort(a, low, i - 1);
        quickSort(a, i + 1, high);
    }

    private static int adjustArray(int[] a, int low, int high) {
        int tmp = a[low];
        while (low < high) {
            while (low < high && a[high] >= tmp) {
                high--;
            }
            if (low < high) {
                a[low++] = a[high];
            }
            while (low < high && a[low] < tmp) {
                low++;
            }
            if (low < high) {
                a[high--] = a[low];
            }
        }
        a[low] = tmp;
        return low;
    }

    public static void main(String[] args) {

        int[] a = {49, 38, 65, 97, 76, 13, 27, 49};
        System.out.println(Arrays.toString(a));
        quickSort(a, 0, a.length - 1);
        System.out.println(Arrays.toString(a));

    }
}

python:

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
def adjust_array(low, high):
    temp = a[low]
    while low < high:
        while low < high and a[high] >= temp:
            high -= 1
        if low < high:
            a[low] = a[high]
            low += 1
        while low < high and a[low] <= temp:
            low += 1
        if low < high:
            a[high] = a[low]
            high -= 1

    a[low] = temp
    return low


def quick_sort(low, high):
    if low >= high:
        return
    mid = adjust_array(low, high)
    quick_sort(low, mid - 1)
    quick_sort(mid + 1, high)
    pass


if __name__ == '__main__':
    a = [5, 4, 5, 7, 9, 2, 1]
    quick_sort(0, len(a) - 1)
    print(a)