算法练习_快速排序

Posted on | Edited on | Comments: | Views:
快速排序的学习笔记以及代码实现

概念

问题描述

给定无序数组，将数组按从小到大的顺序排列。

算法思想

使用分治的思想，首先将一个数组分为两个子数组，将两部分独立地排序。切分的方法是，首先选定一个切分元素，然后从数组的左端开始向右扫描，找到一个大于等于它的元素，再从数组的右端开始向左扫描，找到小于等于它的元素，交换位置。这样扫描完数组之后，切分元素的左子数组均比切分元素小，右子数组均比切分元素大，而切分元素位于中间位置。再运用递归的思想分别对左子数组与右子数组进行快速排序，最终得到有序的数组。

图解

代码实现

clojure

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
(defn get-list [items x y]
  (cond (empty? items) '()
        (= 0 y) (if (> x (first items))
                  (concat (list (first items)) (get-list (rest items) x y))
                  (get-list (rest items) x y))
        :else (if (< x (first items))
                (concat (list (first items)) (get-list (rest items) x y))
                (get-list (rest items) x y))))

(defn quick-sort [items]
  (let [left-itmes (get-list items (first items) 0)]
    (let [right-items (get-list items (first items) 1)]
      (cond (empty? left-itmes) (concat (list (first items)) right-items)
            (empty? right-items) (concat left-itmes (list (first items)))
            :else (concat (quick-sort left-itmes) (list (first items)) (quick-sort right-items))))))

java

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
/**
 * @author zhyee
 * @date 2018/10/27 下午11:35
 */
public class QuickSort {

    public int[] quickSort(int[] a) {
        return quickSort(a,/**base**/0,/**base**/a.length - 1);
    }

    private int[] quickSort(int[] a, int lo, int hi) {
        if (hi <= lo) {
            return a;
        }
        int j = partition(a, lo, hi);
        quickSort(a, lo, j - 1);
        quickSort(a, j + 1, hi);
        return a;
    }

    private int partition(int[] a, int lo, int hi) {
        int v = a[lo];
        int i = lo + 1;
        int j = hi;
        while (true) {
            if (i > j) {
                // exchange a[j],v
                a[lo] = a[j];
                a[j] = v;
                break;
            } else if (a[i] > v && a[j] < v) {
                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;
                i++;
                j--;
            } else if (a[i] > v) {
                j--;
            } else if (a[j] < v) {
                i++;
            } else {
                i++;
                j--;
            }
        }
        return j;
    }
}

特点

  • 快排算法的排序效率依赖于切分数组的效果，而这依赖于切分元素的值。最好的情况是每次都能将数组对半分。
  • 快速排序有一个潜在的缺点，如果第一次从最小元素切分，第二次从最小元素切分，那么数组每次调用只会移除一个元素。为了尽可能避免这种情况，可以在快速排序前将数组随机排序，使产生糟糕切分的可能性降到极低。

参考文档

《算法》