#include <iostream>
#include <ctime>
#include <cmath>
void quickSort(int *array, int first, int last) {
if (first >= last) {
return;
}
int referenceValue = array[(first + last) / 2];
int i = first;
int j = last;
while (i <= j) {
// 如果没有i == j这一步, 则1, 2, 3, 4, 3排序是错误的
while (i <= last && array[i] < referenceValue) {
++i;
}
while (j >= first && array[j] > referenceValue) {
--j;
}
if (i <= j) {
// 如果没有i == j这一步, 则3, 3, 3排序是死循环
int temp = array[i];
array[i] = array[j];
array[j] = temp;
++i;
--j;
}
}
quickSort(array, first, j);
quickSort(array, i, last);
}
int main() {
srand(time(0));
int length = 0;
for (int count = 0; count < 20; ++count) {
length = rand() % 20;
int *array = new int[length];
for (int i = 0; i < length; ++i) {
*(array + i) = rand() % 50;
}
quickSort(array, 0, length - 1);
for (int i = 0; i < length; ++i) {
std::cout << array[i] << ", ";
}
delete[] array;
std::cout << std::endl;
}
return 0;
}
测试结果:
17, 20, 23, 23, 28, 31, 39, 41,
2, 2, 6, 9, 10, 12, 20, 26, 28, 34, 40, 40, 44, 47,
6, 18, 20, 24, 30, 35, 47,
21, 22, 38, 43, 45, 45,
5, 19,
3, 7, 12, 17, 23, 29, 33, 36, 45, 45,
6, 17, 27, 29, 44, 45,
5, 10, 28, 29, 33, 37, 37, 49, 49,
27, 49, 49,
2, 2, 8, 11, 13, 17, 23, 23, 35, 39, 40,
3, 9, 17, 21, 24, 25, 33, 38,
0, 2, 13, 18, 23, 23, 29, 30, 38, 44,
1, 7, 7, 15, 16, 17, 17, 19, 24, 25, 40, 46, 46,
0, 4, 9, 14, 19, 25, 28, 29, 30, 35, 44, 45,
3, 19, 21, 21, 32, 48,
4, 9, 14, 20, 34, 35, 41,
0, 3, 3, 6, 9, 13, 21, 21, 21, 27, 29, 36, 38, 41, 44, 47,
2, 10, 18, 22, 24, 28, 36, 36, 44,
10, 25, 31,
另一种快速排序，更好一点：
// 快速排序是对起泡排序的一种改进
public static void quickSort(int[] array) {
quickSort(array, 0, array.length - 1);
}
public static void quickSort(int[] array, int low, int height) {
if (low < height) {
int pivotLoc = partition(array, low, height);
quickSort(array, low, pivotLoc - 1);
quickSort(array, pivotLoc + 1, height);
}
}
public static int partition(int[] array, int low, int height) {
int temp = array[low];
while (low < height) {
while (low < height && array[height] >= temp) --height;
array[low] = array[height];
while (low < height && array[low] <= temp) ++low;
array[height] = array[low];
}
array[low] = temp;
return low;
}
public static void print(int[] array) {
System.out.print("[");
for (int i = 0; i < array.length - 1; ++i) {
System.out.print(array[i] + ", ");
}
if (array.length - 1 > 0) {
System.out.print(array[array.length - 1]);
}
System.out.print("]");
}