本文主要是介绍introsort的快排跑排序OJ代码，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
introsort的快排跑排序OJ代码
introsort是introspective sort采⽤了缩写，他的名字其实表达了他的实现思路，他的思路就是进⾏⾃ 我侦测和反省，快排递归深度太深（sgi stl中使⽤的是深度为2倍排序元素数量的对数值）那就说明在这种数据序列下，选key出现了问题，性能在快速退化，那么就不要再进⾏快排分割递归了，改换为堆 排序进⾏排序。
void Swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}
void AdjustDown(int* a, int n, int parent)
{int child = parent * 2 + 1;while (child < n){// 选出左右孩⼦中⼤的那⼀个if (child + 1 < n && a[child + 1] > a[child]){++child;}if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}
void HeapSort(int* a, int n)
{// 建堆 -- 向下调整建堆 -- O(N)for (int i = (n - 1 - 1) / 2; i >= 0; --i){AdjustDown(a, n, i);}// ⾃⼰先实现 -- O(N*logN)
int end = n - 1;while (end > 0){Swap(&a[end], &a[0]);AdjustDown(a, end, 0);--end;}
}
void InsertSort(int* a, int n)
{for (int i = 1; i < n; i++){int end = i-1;int tmp = a[i];// 将tmp插⼊到[0,end]区间中，保持有序while (end >= 0){if (tmp < a[end]){a[end + 1] = a[end];--end;}else{break;}}a[end + 1] = tmp;}
}void IntroSort(int* a, int left, int right, int depth, int defaultDepth)
{if (left >= right)return;// 数组⻓度⼩于16的⼩数组，换为插⼊排序，简单递归次数if(right - left + 1 < 16){InsertSort(a+left, right-left+1);return; }// 当深度超过2*logN时改⽤堆排序
if(depth > defaultDepth){HeapSort(a+left, right-left+1);return;}depth++;int begin = left;int end = right;// 随机选keyint randi = left + (rand() % (right-left + 1));Swap(&a[left], &a[randi]);int prev = left;int cur = prev + 1;int keyi = left;while (cur <= right){if (a[cur] < a[keyi] && ++prev != cur){Swap(&a[prev], &a[cur]);}++cur;}Swap(&a[prev], &a[keyi]);keyi = prev;// [begin, keyi-1] keyi [keyi+1, end]IntroSort(a, begin, keyi - 1, depth, defaultDepth);IntroSort(a, keyi+1, end, depth, defaultDepth);
}
void QuickSort(int* a, int left, int right)
{int depth = 0;int logn = 0;int N = right-left+1;for(int i = 1; i < N; i *= 2){logn++;}
// introspective sort -- ⾃省排序IntroSort(a, left, right, depth, logn*2);
}
int* sortArray(int* nums, int numsSize, int* returnSize){srand(time(0));QuickSort(nums, 0, numsSize-1);*returnSize = numsSize;return nums;
}
这个方法比较神的地方在于可以适用于绝大多数情况
这篇关于introsort的快排跑排序OJ代码的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
