做网站优化的协议书,制作图,专业的高端网站制作公司,用手机怎么做免费网站快排性能的关键点分析
决定快排性能的关键点是每次单趟排序后#xff0c;key对数组的分割#xff0c;如果每次选key基本⼆分居中#xff0c;那么快排的递归树就是颗均匀的满⼆叉树#xff0c;性能最佳。但是实践中虽然不可能每次都是⼆分居中#xff0c;但是性能也还是可…快排性能的关键点分析
决定快排性能的关键点是每次单趟排序后key对数组的分割如果每次选key基本⼆分居中那么快排的递归树就是颗均匀的满⼆叉树性能最佳。但是实践中虽然不可能每次都是⼆分居中但是性能也还是可控的。但是如果出现每次选到最小值/最大值划分为0个和N-1的子问题时时间复杂度为O(N^2)数组序列有序时就会出现这样的问题但是当数组中有大量重复数据时之前的快速排序方法就会比较慢因此我们需要更进算法。
三路排序
三路划分算法思想讲解 当面对有大量跟key相同的值时三路划分的核心思想有点类似hoare的左右指针和lomuto的前后指针的结合。核心思想是把数组中的数据分为三段 [比key小的值]、[跟key相等的值] 、[比key大的值]所以叫做三路划分算法。结合下图理解⼀下实现思想
key默认取left位置的值。left指向区间最左边right指向区间最右边cur指向left1位置。cur遇到比key小的值后跟left位置交换换到左边leftcur。cur遇到比key大的值后跟right位置交换换到右边right--。cur遇到跟key相等的值后cur。直到curright结束 #includestdio.h
#includetime.h
#includestdlib.hvoid swap(int* x, int* y)
{int tmp *x;*x *y;*y tmp;
}void Print(int* a, int n)
{for (int i 0; i n; i){printf(%d ,a[i]);}printf(\n);
}void QuickSort(int* a, int left,int right)
{if (left right)return;//随机选keyint randi left (rand() % (right - left 1));swap(a[left], a[randi]);int begin left;int end right;int key left;int cur left 1;while (cur right){if (a[cur] a[key]){swap(a[cur],a[left]);cur;left;}else if (a[cur] a[key]){swap(a[cur], a[right]);right--;}else if (a[cur] a[key]){cur;}}QuickSort(a,begin,left-1);QuickSort(a, right 1, end);
}int* sortArray(int* nums, int numsSize, int* returnSize)
{srand((unsigned int)time(NULL));QuickSort(nums, 0, numsSize - 1);*returnSize numsSize;return nums;
}int main()
{int arr[] {2,5,7,6,1,4,3,9,8};int n sizeof(arr) / sizeof(arr[0]);Print(arr,n);int* tmpsortArray(arr, n,n);Print(tmp, n);return 0;
}自省排序 introsort
自省排序的思路就是进行自我侦测和反省快排递归深度太深sgi stl中使用的是深度为2倍排序元素数量的对数值那就说明在这种数据序列下选key出现了问题性能在快速退化那么就不要再进行快排分割递归了改换为堆排序进行排序。
#includestdio.h
#includetime.h
#includestdlib.hvoid Print(int* a, int n)
{for (int i 0; i n; i){printf(%d ,a[i]);}printf(\n);
}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);}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;int 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;IntroSort(a, begin, keyi - 1, depth, defaultDepth);IntroSort(a, keyi 1, end, depth, defaultDepth);
}void QuickSort(int* a, int left, int right)
{int logn 0;int depth 0;int N right - left 1;for (int i 1; i N; i * 2){logn;}IntroSort(a, left, right, depth, logn * 2);
}int* sortArray(int* nums, int numsSize, int* returnSize)
{srand((unsigned int)time(NULL));QuickSort(nums, 0, numsSize - 1);*returnSize numsSize;return nums;
}int main()
{int arr[] {2,5,7,6,1,4,3,9,8};int n sizeof(arr) / sizeof(arr[0]);Print(arr,n);int* tmpsortArray(arr, n,n);Print(tmp, n);return 0;
}
