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
private static void qSort(int[] a,int left,int right){
    if(left < right){
        int mid = divide(a,left,right);
        qSort(a,left,mid);
        qSort(a,mid+1,right);
    }
}

private static int divide(int[] a,int left,int right){
    int mid = left;

    while(left < right) {
        while (left < right && a[right] >= a[mid]) {
            right--;
        }
        while (left < right && a[left] < a[mid]) {
            left++;
        }
        if (left < right) {
            swap(a, left, right);
        }
    }
    return left;
}

private static void swap(int[] a, int left, int right) {
    int tmp = a[left];
    a[left] = a[right];
    a[right] = tmp;
}

具体流程：

  1. 定义两个指针left和right代表两个初始化位置，分别表示需要排序数组的最左和最右。
  2. 一直遍历，right向左移动，直到找到小于中枢值的位置。
  3. 一直遍历，left向右移动，直到找到大于中枢值的位置。
  4. 如果left<right，交换这两个元素。
  5. 重复上面步骤。
  6. 使用递归再对两边子数组进行排序。

非递归实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//    非递归实现快排
    private static void qSort2(int[] a,int left,int right){
        Stack<Integer> s = new Stack<>();
        s.push(left);
        s.push(right);

        while(!s.isEmpty()){
            int r = s.pop();
            int l = s.pop();
            int mid = divide(a,l,r);
            if(l < mid){
                s.push(l);
                s.push(mid);
            }
            if(mid + 1 < right){
                s.push(mid+1);
                s.push(right);
            }
        }
    }

对需要排序的数组的左指针和右指针l、r记录起来，压入到栈中，每次循环都会弹出一对l、r。
当栈为空时，说明都已经排序了。接收循环。