对大量元素执行快速排序的 C++ 程序
快速排序技术是通过将列表分成两部分来完成的。最初通过分区算法选择一个枢轴元素。枢轴的左侧部分保存比枢轴小的值，右侧部分保存较大的值。分区后，每个单独的列表都使用相同的过程进行分区。
这里我们考虑对一个大数组（近100个元素）进行排序。我们正在取一些数字，然后以随机顺序对它们进行洗牌，使它们未排序。然后使用快速排序技术进行排序。
快速排序技术的复杂性
时间复杂度-O(nlogn)对于最佳情况和平均情况，最坏情况为O(n2)。
空间复杂度-O(logn)
输入 -未排序列表：904522112250
输出 -排序后的数组：112222455090
算法
partition(array,lower,upper)
输入-数据集数组，下边界和上边界
输出-在正确的位置枢轴
Begin
pivot := array[upper]
i := lower – 1
for j in range lower to higher, do
if array[j] < pivot, then
exchange the values of array[i] and array[j]
i := i + 1
done
exchange the values of array[upper] and array[i + 1]
return i + 1
EndquickSort(array,left,right)
输入-数据数组，以及数组的下限和上限
输出-排序后的数组
Begin if lower < right then q = partition(array, left, right). quickSort(array, left, q-1) quickSort(array, q+1, right) End
示例代码
#include输出结果#include #include #define MAX 100 using namespace std; void random_shuffle(int arr[]) { //将数组元素打乱到随机位置的函数 srand(time(NULL)); for (int i = MAX - 1; i > 0; i--) { int j = rand()%(i + 1); int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } int partion(int arr[], int p, int r) { int pivot = arr[r]; //最后一项作为枢轴 int i = p - 1; for (int j = p; j < r; j++) { if (arr[j] < pivot) { i++; swap(arr[i], arr[j]); } } swap(arr[i+1], arr[r]); return i + 1; } void quick_sort(int arr[], int p, int q) { //递归排序列表 int j; if (p < q) { j = partion(arr, p, q); quick_sort(arr, p, j - 1); quick_sort(arr, j + 1, q); } } int main() { int i; int arr[MAX]; for (i = 0;i < MAX;i++) arr[i] = i + 1; random_shuffle(arr); //随机化数组 quick_sort(arr, 0, MAX-1); //对数组元素进行排序 for (i = 0; i < MAX;i++) cout << arr[i] << " "; cout << endl; return 0; }
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 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100