经典算法什么是 快速排序

  • A+
所属分类:JAVA编程

一、快速排序介绍
百度百科是这样介绍快速排序的:

二、快速排序的算法思想
将小于基准点的元素放到基准点的左边,将大于基准点的元素放到基准点的右边。经过过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,让所有的数据变成有序的。

其实快速排序算法是基于一种“二分法”的思想,关于二分法的算法可以参考另一篇博客 经典算法(2)一文搞懂二分法查找(循环和递归两种方式),有关冒泡排序的算法参考 经典算法(1)冒泡排序及其优化

冒泡排序每次只能在相邻的数之间进行交换,如果有10个数字,就需要排序9轮。但是按照快速排序的思想进行排序,总的比较和交换次数减少了,排序速度也会提升。

三、快速排序的实现过程
我们取第一个数字为基准元素,在此博客中演示的例子中,基准元素取为6;设置两个指针 i 和 j,它们分别指向数组的第一个元素和数组最后一个元素,即i=0,j=9。

首先让指针 j 开始向左挪动,直到找到一个小于6的数停下来。切换到指针 i 再向右挪动,直到找到一个数大于6的数停下来。

最后指针 j 停在了数字 1上,指针 i 停在了数字8上。让指针 i 和指针 j 指向的元素进行交换位置。

第一次排序完成,接着进行第2次排序,指针 j 继续向左移动,由于3 < 6 ,指针 j 停下来;接着指针 i 开始向右继续移动,由于 9 > 6,停下来,9与3进行交换位置。

第2次排序结束,继续进行第3次排序,指针 j 继续向左移动,移动到数字5的位置,由于5 < 6 ,指针 j 停下来;接着指针 i 开始向右继续移动,此时 指针 i 与 指针 j 重合,把重合点的元素5与基准元素6交换位置,这一轮循环停止执行。

四、代码实现
public class QuickSort {
public static void main(String[] args) {
int[] array = {6, 2, 4, 8, 9, 5, 7, 3, 1, 10};
System.out.println("排序之前的数组: " + Arrays.toString(array));
quickSort(array, 0, array.length - 1);
System.out.println("排序之后的数组: " + Arrays.toString(array));
}


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
61
62
63
private static void quickSort(int[] array, int startIndex, int endIndex) {
    if (startIndex &lt; endIndex) {
        // 找基准元素
        int baseIndex = divide(array, startIndex, endIndex);
        // 递归调用,对分隔后的左边数组快速排序
        quickSort(array, startIndex, baseIndex - 1);
        // 递归调用,对分隔后的右边数组快速排序
        quickSort(array, baseIndex + 1, endIndex);
    } else {
        return;
    }
}

/**
 * 利用双边循环法分隔数组
 *
 * @param array      需要排序的数组
 * @param startIndex 数组的开始下标
 * @param endIndex   数组的结束下标
 * @return 返回分隔点所在的位置
 */
private static int divide(int[] array, int startIndex, int endIndex) {
    // 用数组的第一个元素作为起始元素
    int base = array[startIndex];
    int i = startIndex;
    int j = endIndex;
    while (i != j) {
        // 从右向左寻找第一个小于基准数的值
        while (i &lt; j &amp;&amp; array[j] > base) {
            j--;
        }
        // 从左向右寻找第一个大于基准数的值
        while (i &lt; j &amp;&amp; array[i] &lt;= base) {
            i++;
        }
        // 交换位置
        if (i &lt; j) {
            swap(array, i, j);
        }
    }

    // 指针i 与指针j 相遇,把重合点的元素与基准元素交换位置
    array[startIndex] = array[i];
    array[i] = base;

    // 返回分隔点所在的位置
    return i;
}

/**
 * 交换i 与 j 位置的值
 *
 * @param array
 * @param i
 * @param j
 */
private static void swap(int[] array, int i, int j) {
    int temp;
    temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}
}

排序之前的数组: [6, 2, 4, 8, 9, 5, 7, 3, 1, 10]
排序之后的数组: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

avatar

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: