快速排序总结
1. 随机数做Pivot
#include <iostream>#include <ctime>void swap(int* a, int* b){if (a == b)return;*a = *a ^ *b;*b = *a ^ *b;*a = *a ^ *b;};int partition(int* a, int left, int right){int pivot = (left + right) / 2;//Median from 3 numbersif (a[left] > a[pivot])swap(&a[left], &a[pivot]);if (a[left] > a[right])swap(&a[left], &a[right]);if (a[pivot] > a[right])swap(&a[pivot], &a[right]);swap(&a[pivot], &a[right]);int front = left;int curIdx = left;while (curIdx < right){if (a[curIdx] < a[right])swap(&a[curIdx], &a[front++]);curIdx++;}swap(&a[front], &a[right]);return front;};void quickSort(int* a, int left, int right){if (left < right){int pivot = partition(a, left, right);quickSort(a, left, pivot - 1);quickSort(a, pivot + 1, right);}};int main(){int a[10] = {10, 9, 8, 7, 6, 55, 11, 5, 3, 2};quickSort(a, 0, sizeof(a) / sizeof(int) - 1);return 0;}