快速排序（quick sort）

基本思路：快速排序每次只排定一个元素（也就是每次只把一个数放在它最终应该在的位置），然后递归的排这个数的左边和右边，直到整个数组有序。

public int[] Sort(int[] array) {
    // corner case
    if (array == null || array.length <= 1) {
        return array;
    }
    // 使用快排排序
    quickSort(array,0,array.length-1);
    return arary;
}

// 定义quickSort函数，每次排一个数（确定一个数的位置），然后递归排这个数左边和右边
public void quickSort(int[] array,int left,int right) {
    // base case
    if (left >= right) {
        return;
    }
    // 排一个数
    int p = partition(array,left,right);
    // 递归，排p所在数的左和右
    quickSort(array,left,p-1);
    quickSort(array,p+1,right);
}

// 定义partition函数 ：排好一个数的位置，并返回它的位置（即左边全是比它小的，右边全是比它大的）
public Random rd = new Random();
public int partition(int[] array,int left,int right) {

    // step 1 : 先在left-right随机一个数，然后把这个数放到一个固定位置（不重要，只是为了后面作
    // 比较的时候方便找），一般放到left或right
    int pivotIndex = rd.nextInt(right - left + 1) + left;
    swap(array,pivotIndex,right); // 先暂放最右边
    
    // step 2 : 找到pivot的正确位置（p），（即左边全是比它小的，右边全是比它大的）
    int i = left;
    int j = right - 1; // right是pivot不用比较
    while (i <= j) {   // i = j的时候还有一个元素没判断
        if (array[i] < array[right]) {
            i++;
        }
        else {
            swap(array,i,j);
            j--;
        }
    }
    
    // step 3 : 排完序把pivot换回去(此时应该是right和i（i，j里面大的一个）换)
    // 注意最后一次i == j ，循环结束后i在j的右边一个（同时也是base case（left >= right））
    // 此时i所在的值比j所在的值大
    swap(array,right,i);
    return i; // i就是最终pivot所在的正确位置
}

// 定义swap函数
public void swap(int[] array,int x,int y) {
    int temp = array[x];
    array[x] = array[y];
    array[y] = temp;
}
    
    

主要就是在递归排序时，首先找出一个数，找到它的正确位置，然后再递归排这个数的左边和右边。

--首先找这个数的正确位置，体现在程序中的partition（）函数。

最后

以上就是结实汉堡为你收集整理的快速排序（quick sort）的全部内容，希望文章能够帮你解决快速排序（quick sort）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。