排序算法一、插入排序1. 思想是——逐个将未排序的数据插入到已排序的数据中2. 重要性——为ON中效率较快的排序方法是理解希尔排序的根基3. 代码for (int i 1; i n; i){int tmp a[i];int j i - 1;while(j 0 a[j] tmp){a[j 1] a[j];--j;}a[j 1] tmp;}4. 时间复杂度分析—有序——ON无序——ON^2时间复杂度为ON^2二、希尔排序1. 思想是——紧接着插入排序在插入排序实践中意识到排序前的数据越有序插入排序执行的越快所以考虑到要进行预排序2. 预排序的处理——以特定的间距取数据进行插入排序3. 代码for (int gap 3; gap 1; gap--){for (int i gap; i n; i gap){int tmp a[i];int j i - gap;while (a[j] tmp j 0){a[j gap] a[j];j-gap;}a[j gap] tmp;}}4. 时间复杂度——在排序时复杂度先增加后减少最大的一遍不过N总的来说时间复杂度为ON^1.3三、选择排序1. 思想是——遍历数据选择出最大和最小的数据分别与尾头交换在最大和最小值相等时结束2. 代码for (int i 0; i n/2; i){int imin i;int imax n - 1 - i;if (imin imax){break;}for (int j i; j n - i; j){if (a[j] a[imax]){imax j;}if (a[j] a[imin]){imin j;}}if (imax i imin n - 1 - i){Swap(a[i], a[n - 1 - i]);}else if (imax i){Swap(a[n - 1 - i], a[imax]);Swap(a[i], a[imin]);}else{Swap(a[i], a[imin]);Swap(a[n - 1 - i], a[imax]);}}3. 时间复杂度——ON^2四、堆排序1. 思想是——排升序是建大堆将头尾数据交换在向下排序直到有序2. 代码int i tail / 2;while (i 0){AdjustDwon(a, n, i1);i--;}while(tail 0){Swap(a[0], a[tail]);AdjustDwon(a, tail, 1);tail--;}3. 优势——时间复杂度稳定适合完成大数据的排序4. 时间复杂度——Onlogn五、快速排序1. 思想是——取定key值将小于key的排在key左侧大于key的排在右侧2. 代码1使用递归实现的具有随机取中和小区间优化的自省排序// 快速排序hoare版本int PartSort1(int* a, int left, int right){int begin left;int end right;int key a[left];while (end begin){while (end begin a[end] key ){end--;}while (end begin a[begin] key){begin;}Swap(a[begin],a[end]);}Swap(a[left],a[end]);return end;}// 快速排序挖坑法int PartSort2(int* a, int left, int right){int begin left;int end right;int key a[left];int index left;while (end begin){while (end begin a[end] key){end--;}if (end begin){Swap(a[index], a[end]);index end;}while (end begin a[begin] key){begin;}if (end begin){Swap(a[begin], a[index]);index begin;}}a[index] key;return index;}// 快速排序前后指针法int PartSort3(int* a, int left, int right){int key a[left];int prev left;int cur left 1;while (cur right){if (a[cur] key){prev;Swap(a[prev], a[cur]);}cur;}Swap(a[prev], a[left]);return prev;}//自省排序void Introsort(int* a, int left, int right, int depth, int wanteddepth){depth;if (left right){return;}if (depth wanteddepth){HeapSort(a left, right - left 1);return;}if (right - left 1 10){InsertSort(a left, right - left 1);return;}GetMid(a, left, right);int mid PartSort3(a, left, right);Introsort(a, left, mid - 1, depth, wanteddepth);Introsort(a, mid 1, right, depth, wanteddepth);}2三路划分实现//三路划分void ThreeWayPartitionint(int* a, int left, int right){if (left right){return;}if (right - left 1 10){InsertSort(a left, right - left 1);return;}GetMid(a, left, right);int end right;int key a[left];int prev left;int cur left 1;while (cur right){if (a[cur] key){Swap(a[cur], a[prev]);prev;cur;}else if (a[cur] key){Swap(a[cur], a[right]);right--;}else{cur;}}ThreeWayPartitionint(a,left, prev - 1);ThreeWayPartitionint(a,cur, end);}3非递归实现void QuickSortNonR(int* a, int left, int right){if (left right){return;}Queue q;QueueInit(q);GetMid(a, left, right);int mid PartSort2(a, left, right);if (left mid - 1){QueuePush(q, left);QueuePush(q, mid - 1);}if (mid 1 right){QueuePush(q, mid 1);QueuePush(q, right);}while (!QueueEmpty(q)){left QueueFront(q);QueuePop(q);right QueueFront(q);QueuePop(q);if (right - left 1 10){InsertSort(a left, right - left 1);continue;}GetMid(a, left, right);mid PartSort2(a,left, right);if (left mid - 1){QueuePush(q, left);QueuePush(q, mid - 1);}if (mid 1 right){QueuePush(q, mid 1);QueuePush(q, right);}}QueueDestroy(q);}3. 时间复杂度——Onlogn4. 优点综合性能强优化后几乎不见ON^2情况