当前位置: 首页> 健康> 母婴 > 在线设计平台用户规模_珠海百度推广优化_360seo关键词优化_排名第一的手机清理软件

在线设计平台用户规模_珠海百度推广优化_360seo关键词优化_排名第一的手机清理软件

时间:2025/7/9 14:40:38来源:https://blog.csdn.net/a15670247200/article/details/143532894 浏览次数:0次
在线设计平台用户规模_珠海百度推广优化_360seo关键词优化_排名第一的手机清理软件

一.快速排序补充

快速排序的分治部分还有其他方法,如挖坑法,快慢指针法。

1.挖坑法(重要)

思路:先将基准位置元素用tmp保存,假定基准位置没有值(有个坑),然后分别从前后向中间遍历,右边大于基准就减减,遇到小于基准的就放到基准值位置的坑中,左边亦然,遍历整个数组后,将基准值填入最后一个左边遍历值。

    //挖坑法public static int partition2(int[] array,int start,int end) {int pivot = array[start];int i = start;while(start < end) {while(start < end && array[end] >= pivot) {end--;}array[start] = array[end];while(start < end && array[start] <= pivot) {start++;}array[end] = array[start];}array[start] = pivot;return start;}

细节注意:填坑不是互换

2.快慢指针法

通过建立两个指针,一个满足小于基准值++,另一个在前一个指针不大于基准时++,大于后不再++;从而与前一个快指针换位。

//快慢指针法public static int partition3(int[] array,int start,int end) {int prev = start;int cur = start+1;while(cur <= end) {if(array[cur] < array[start] && array[cur] != array[++prev]) {swap(array,prev,cur);}cur++;}//把最后一个小于[prev]的值换到开头swap(array,prev,start);return prev;//start不行}

3.非递归法快速排序实现

思路:反复利用栈的push,pop来实现递归的效果。核心就是把分别把要排序的数据的left,right压入栈,在排序时弹出用于排序。

    public static void quickSort2(int[] array) {int left = 0;int right = array.length-1;int par = partition3(array,left,right);Stack<Integer> stack = new Stack<>();if(par > left+1) {//left+1是为了保证最少左边右一个元素stack.push(left);stack.push(par-1);}if(par < right-1) {//right-1是为了stack.push(par+1);stack.push(right);}while(!stack.empty()) {right = stack.pop();left = stack.pop();par = partition3(array,left,right);if(par > left+1) {//left+1是为了保证最少左边右一个元素stack.push(left);stack.push(par-1);}if(par < right-1) {//right-1是为了stack.push(par+1);stack.push(right);}}}
时间复杂度: O(N*logN)
空间复杂度: O(logN)
稳定性:不稳定

二.归并排序(递归)

思想:

采用分治法的一个非常典型的应用,将数组分解成若干子列,先使若干子列有序,再进行合并操作递归使整个数组有序。

 1.分解

     利用中间值mid递归分解

    public static void mergeSortFunc(int[] array,int left,int right) {if(left == right) {return;}int mid = (left + right) / 2;//分解mergeSortFunc(array,left,mid);mergeSortFunc(array,mid+1,right);}

最终分解结果是各子列被分解为长度不超过2的单元

2.合并

先对最终子列排序,之后沿用这个方法递归得数组。

    public static void merge(int[] array,int left,int mid,int right) {int s1 = left;int e1 = mid;int s2 = mid+1;int e2= right;int k = 0;int[] tmpArray = new int[right - left + 1];while(s1 <= e1 && s2 <= e2) {if(array[s1] <= array[s2]) {tmpArray[k++] = array[s1++];}else {tmpArray[k++] = array[s2++];}}while(s1 <= e1) {tmpArray[k++] = array[s1++];}while(s2 <= e2){tmpArray[k++] = array[s2++];}for (int i = 0; i < tmpArray.length; i++) {array[i + left] = tmpArray[i];}}

总代码:

    public static void mergeSort1(int[] array) {mergeSortFunc(array,0,array.length-1);}public static void mergeSortFunc(int[] array,int left,int right) {if(left == right) {return;}int mid = (left + right) / 2;//分解mergeSortFunc(array,left,mid);mergeSortFunc(array,mid+1,right);//合并merge(array,left,mid,right);}public static void merge(int[] array,int left,int mid,int right) {int s1 = left;int e1 = mid;int s2 = mid+1;int e2= right;int k = 0;int[] tmpArray = new int[right - left + 1];while(s1 <= e1 && s2 <= e2) {if(array[s1] <= array[s2]) {tmpArray[k++] = array[s1++];}else {tmpArray[k++] = array[s2++];}}while(s1 <= e1) {tmpArray[k++] = array[s1++];}while(s2 <= e2){tmpArray[k++] = array[s2++];}for (int i = 0; i < tmpArray.length; i++) {array[i + left] = tmpArray[i];}}
 

时间复杂度:O(n*logN)

空间复杂度:O(n)

 稳定性:稳定性

三.归并排序(非递归)

思路:手动分组,利用for循环将数组分解成若干子列,在分解过程中排好序,再循环回原数组。

分解:

    public static void mergeSort2(int[] array) {int gap = 1;while(gap < array.length) {for (int i = 0; i < array.length; i+=2*gap) {int left = i;int mid = left + gap - 1;int right = mid + gap;if(mid >= array.length) {mid = array.length-1;}if(right >= array.length) {right = array.length-1;}}gap *= 2;}}

注意:mid,right可能会越界。

合并:因为分解是从最小子列开始,所以可以在每次循环中排序合并。

    public static void mergeSort2(int[] array) {int gap = 1;while(gap < array.length) {for (int i = 0; i < array.length; i+=2*gap) {int left = i;int mid = left + gap - 1;int right = mid + gap;if(mid >= array.length) {mid = array.length-1;}if(right >= array.length) {right = array.length-1;}merge(array,left,mid,right);}gap *= 2;}}

四.计数排序(了解)

将要统计元素大小作为数组下标,通过统计要排序的元素的个数,然后按顺序打印统计数组元素遍的数组下标,完成排序。

    public static void countSort(int[] array) {int min = array[0];int max = array[0];for (int i = 0; i < array.length; i++) {if(array[i] < min) {min = array[i];}if(array[i] > max) {max = array[i];}}int len = max - min + 1;int[] tmpArray = new int[len];//制作计数数组for (int i = 0; i < array.length; i++) {tmpArray[array[i] - min]++;}//完成排序int Index = 0;for (int i = 0; i < len; i++) {while(tmpArray[i] != 0) {array[Index++] = i + min;tmpArray[i]--;}}}

关键字:在线设计平台用户规模_珠海百度推广优化_360seo关键词优化_排名第一的手机清理软件

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: