快速排序模板

Algorithm

发布日期: 2021-03-03

更新日期: 2022-07-31

文章字数: 734

阅读时长: 3 分

阅读次数:

引言：

快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高，因此经常被采用。

说明

快速排序算法经常被采用，而且快速排序也采用了分治的思想，因此很多软件公司的笔试面试，包括像腾讯，微软等知名IT公司都喜欢考这个，还有大大小的程序方面的考试如软考，考研中也常常出现快速排序的身影。
总的说来，要直接默写出快速排序还是有一定难度的，以下为快速排序的模板，希望对大家快速上手有帮助，达到快速排序，快速搞定的效果。

该方法的基本思想是：

先从数列中取出一个数作为基准数。（通常就取最左边的数作为基准）

分区过程，将比这个数小的数全放到它的左边，大于或等于它的数全放到它的右边。（并不是很严谨）

再对左右区间重复第二步，直到各区间只有一个数。

模板一(左右挖坑互填)

public void quickSort(int[] s, int l, int r) {
    if (l < r) {
    	//Swap(s[l], s[(l + r) / 2]); //将中间的这个数和第一个数交换。参见注1
        int i = l, j = r;
        int x = s[l];
        while (i < j) {
            while (s[j] >= x && i < j) j--; // 从右向左找第一个小于x的数
            if (i < j) s[i++] = s[j];
            while (s[i] < x && i < j) i++;  // 从左向右找第一个大于等于x的数
            if(i<j) s[j--] = s[i];
        }
        s[i] = x;
        quickSort(s, l, i - 1); //递归调用
        quickSort(s, i + 1, r);
    }
}

模板二(左右交换)

public void quickSort(int[] s, int l, int r) {
    if (l < r) {
        int i = l, j = r;
        int temp = s[i];
        while (i < j) {
            while (s[j] >= s[l] && i < j) j--;
            while (s[i] <= s[l] && i < j) i++;
            temp = s[i]; //交换i、j位置元素
            s[i] = s[j];
            s[j] = temp;
        }
        s[i] = s[l]; //交换i、l位置元素
        s[l] = temp;
        quickSort(s, l, i - 1); //递归调用
        quickSort(s, i + 1, r);
    }
}

模板三(顺序遍历交换)

public void quickSort(int[] s, int l, int r) {
    if (l < r) {
        int base = s[l];//选取一个基准
        int index = l;
        for (int i = index + 1; i <= r; i++) {
            if (s[i] >= base) continue;
            index++;
            //交换
            int temp = s[i];
            s[i] = s[index];
            s[index] = temp;
        }
        s[l] = s[index];
        s[index] = base;
        quickSort(s, l, index - 1);
        quickSort(s, index + 1, r);
    }
}