# 快速排序

## 代码实现

```    public static void main(String[] args) {
int[] a = {9, 45, 10, 35, 64, 99, 103, 56, 47, 12, 79, 0};
sort(a, 0, a.length - 1);
}

public static void sort(int[] arr, int left, int right) {
if (right <= left)
return;
}
int t = partition(arr, left, right);
sort(arr, left, t - 1);
sort(arr, t + 1, right);
}

public static int partition(int[] arr, int left, int right) {
int i = left;
int j = right + 1;
int t = arr[left];
while (true) {
while (arr[++i] < t) {
if (i == right) {
break;
}
}
while (arr[--j] > t) {
if (j == left) {
break;
}
}
if (i >= j) {
break;
}
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
int temp = arr[left];
arr[left] = arr[j];
arr[j] = temp;
return j;
}```

## 三向切分快速排序

```    public static void main(String[] args) {
int[] a = {4, 1, 90, 14, 50, 64, 70, 7, 12, 36, 97, 43, 21, 12};
sort(a, 0, a.length - 1);
System.out.println(Arrays.toString(a));
}

public static void sort(int[] arr, int left, int right) {
if (right <= left) {
return;
}
int i = left, j = right, k = left + 1;
int M = arr[left];
while (k <= j) {
if (arr[k] < M) {
int temp = arr[i];
arr[i] = arr[k];
arr[k] = temp;
i++;
k++;
} else if (arr[k] > M) {
int temp = arr[k];
arr[k] = arr[j];
arr[j] = temp;
j--;
} else {
k++;
}
sort(arr, left,  i- 1);
sort(arr, j + 1, right);
}
}```

## 三数取中法

```    public static void main(String[] args) {
int[] a = {9, 45, 10, 35, 64, 99, 103, 56, 47, 12, 79, 0};
sort(a, 0, a.length - 1);
for (int tt : a) {
System.out.print(tt+" ");
}
}

public static void sort(int[] arr, int left, int right) {
if(right<=left) {
return;
}
threeSplit(arr, left, right);
int i = left, j = right - 1, t = right - 1;
while (true) {
while (arr[++i] < arr[t]) {
if (i == right) {
break;
}
}
while (j>left&&arr[--j] > arr[t]) {
if (j == left) {
break;
}
}
if (i >= j) {
break;
}
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
if (i < right) {
int temp = arr[i];
arr[i] = arr[right - 1];
arr[right - 1] = temp;
}
sort(arr, left, i - 1);
sort(arr, i + 1, right);
}

public static void threeSplit(int[] arr, int left, int right) {
int mid = (left + right)>>>1;
if (arr[left] > arr[mid]) {
int temp = arr[left];
arr[left] = arr[mid];
arr[mid] = temp;
}
if (arr[left] > arr[right]) {
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}
if (arr[mid] > arr[right]) {
int temp = arr[mid];
arr[mid] = arr[right];
arr[right] = temp;
}
int temp = arr[right-1];
arr[right - 1] = arr[mid];
arr[mid] = temp;
}```

# 总结

0 条评论

• ### 排序算法之归并排序

归并排序是一种非常优秀的排序算法，时间复杂度仅为O(nlogn)，与选择排序和冒泡排序的O(n2)相比较，只是将n这个因子替换成了logn，但这是非常划算的一个...

• ### codeforces 1436C（二分+数学）

由于二分是通过不断缩减寻找区间的操作，所以我们可以模拟二分操作，求出二分结束后位置停留在pos时的向左跳的次数left和向右跳的次数right，最后通过组合数来...

• ### 关于动态规划的练习题

1.给出不同面额的硬币以及一个总金额. 写一个方法来计算给出的总金额可以换取的最少的硬币数量. 如果已有硬币的任意组合均无法与总金额面额相等, 那么返回 -1。

• ### 一看就懂的快速排序

快速排序属于交换排序，主要步骤是使用基准元素进行比较，把小于基准元素的移动到一边，大于基准元素的移动到另一边。从而把数组分成两部分，然后再从这两部分中选取出基准...

• ### 排序算法

基本思想: 我们将一个待排序序列分为有序区和无序区（一般开始的时候将第一个元素作为有序区，剩下的元素作为无序区），每次将无序区的第一个元素作为待插入记录，按大小...

• ### 详解快速排序算法

本文的思路是以从小到大为例讲的。 快速排序的基本思想是任取待排序序列的一个元素作为中心元素(可以用第一个，最后一个，也可以是中间任何一个)，习惯将其称为pivo...

• ### [Go] Golang练习项目-快速排序的GO语言实现

快速排序首先选一个基准（你也可以认为是要放到排序后数组正确位置的元素）pivot，然后将数组按照选取的基准 pivot 进行划分。而选取 pivot 的方式又有...

• ### 快速排序与寻找第k小的数算法

慕课网 首发了，放在垂直领域吧。简书备份。 出现了一点小问题，就是index，要注意。想法网上一大堆，不多说了。 ubuntu18下输入法有问题，sogou...

• ### Java中获取一个数组的最大值和最小值

3，然后对数组进行遍历循环，若循环到的元素比最大值还要大，则将这个元素赋值给最大值；同理，若循环到的元素比最小值还要小，则将这个元素赋值给最小值；

• ### 排序算法算法对比

排序大的分类可以分为两种：内排序和外排序。在排序过程中，全部记录存放在内存，则称为内排序，如果排序过程中需要使用外存，则称为外排序。下面讲的排序都是属于内排序。...