文章目录
排序
1.概念
排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
平时的上下文中，如果提到排序，通常指的是排升序（非降序）。
通常意义上的排序，都是指的原地排序(in place sort)
稳定性
两个相等的数据，如果经过排序后，排序算法能保证其相对位置不发生变化，则我们称该算法是具备稳定性的排序算
法。
1.插入排序
附上代码
publicstaticvoidinserSort(int[] array){int i =0;int j =0;for(i =0;i<array.length;i++){//创建一个 遍历tmp存储当前 array[i] 的值int tmp = array[i];for(j = i-1;j>=0;j--){// j 从 i - 1 的 位置开始遍历if(array[j]>tmp){
array[j+1]= array[j];}else{// 此时 array[j] < tmp;// 只要j回退的时候，遇到了比tmp 小的元素就结束这次的比较// array[j+1] = tmp 这就可以放在下面完成赋值break;}}// 走到这里 说明 j == 0，那么 就需要将 tmp 赋值给 0位置
array[j+1]= tmp;}}
接下来 我们继续
插入 排序 的 时间复杂度 为 O(N^2)
最好的情况下 时间复杂度 为 O(N) 这里数据 为 有序的情况下
如 1 2 3 4 5 这 就 j 就 不会 往 回 走 所以 时间 复杂度 为 O(N)
根据上面这个 可以 推出 对于直接插入排序来说，数据越有序，排序越快
空间 复杂度 为 O(1)
插入排序的稳定性 插入排序 是 稳定的
2.希尔排序
我们 刚刚 学习 了 插入 排序 ，那么 希尔排序是 在 插入排序的基础上优化而来。
回忆一下我们 我们 是不是 得出 插入排序的时间复杂度是O(N^2)
如果 是排序 有序的数据那么时间复杂度不就成为了O(N)了。
这里结论不就是 越有序，排序越快。
接下来 我们 代码实现 希尔排序
publicstaticvoidshell(int[] array,int gap){int j =0;for(int i = gap;i<array.length;i++){int tmp = array[i];for(j = i - gap;j>=0;j = j-gap){if(array[j]> tmp){
array[j+gap]= array[j];}else{break;}}
array[j+gap]= tmp;}}publicstaticvoidshellSort(int[] array){int gap = array.length;while(gap >1){shell(array,gap);
gap /=2;}shell(array,1);// 保证最后一组数据是一}
是不是 很像插入排序呀，别看上面分析了那么多 图 ，不过 只是在插入排序上 修改 了 一点东西而已。。
接下来我们 来看一看 希尔排序的 时间复杂度
希尔排序的 时间复杂度
3.选择排序
附上代码
publicstaticvoidswap(int[] array,int i,int j){int tmp = array[i];
array[i]= array[j];
array[j]= tmp;}publicstaticvoidselectSort1(int[] array){for(int i =0;i<array.length;i++){for(int j = i+1;j<array.length;j++){swap(array,i,j);}}}publicstaticvoidselectSort2(int[] array){for(int i =0;i<array.length;i++){int min = i;for(int j = i+1;j<array.length;j++){if(array[j]<array[min]){
min = j;}}swap(array,i,min);}}
这里不管是否优化，这里是时间复杂度 都为 O(N^2)
4.堆排序
堆排序 在 我 堆的 博客中就已经完成，这里就不在画图 推导，这里就直接附上代码
堆博客
附上代码
/**
* 堆排序
*/publicstaticvoidheapSort(int[] array){createHeap(array);int end = array.length -1;while(end >0){swap(array,0,end);shifDown(array,0,end);
end--;}}publicstaticvoidshifDown(int[] array,int parent,int len){int child = parent *2+1;while(child < len){if(child +1< len && array[child]< array[child+1]){
child++;}if(array[parent]< array[child]){swap(array,parent,child);
parent = child;
child =2* parent +1;}else{break;}}}publicstaticvoidcreateHeap(int[] array){for(int parent =(array.length -1-1)/2;parent>=0;parent--){shifDown(array,parent,array.length);}}
5.冒泡排序
想必大家 应该 很熟悉冒泡排序吧，如果不熟悉，这里我们 还是 通过画图 来 让大家熟悉他。
附上代码
publicstaticvoidswap(int[] array,int i,int j){int tmp = array[i];
array[i]= array[j];
array[j]= tmp;}publicstaticvoidbubbleSort1(int[] array){for(int i =0;i<array.length-1;i++){for(int j =0;j<array.length-1-i;j++){if(array[j]> array[j+1]){swap(array,j,j+1);}}}}// 优化publicstaticvoidbubbleSort2(int[] array){for(int i =0;i<array.length-1;i++){boolean flg =true;for(int j =0;j<array.length-1-i;j++){if(array[j]> array[j+1]){
flg =false;swap(array,j,j+1);}}if(flg){break;}}}
冒泡排序的时间复杂度 不管是好是坏 时间复杂度都是O(N^2) 。
空间 复杂度 为 O(1)
稳定 性 ： 冒泡排序是一个稳定的排序
这里 O(N) 其实就是给了 一个 有序的数组， 第二个 循环 if 语句 不会 进入 ，优化 后的 冒泡 排序 第一趟 后就会结束循环
6.快速排序
附上代码
publicstaticvoidquickSort(int[] array){quick(array,0,array.length-1);}publicstaticvoidquick(int[] array,int start,int end){if(start >= end){return;}// 这start 和 end 形参的值 改变了 而 我们 实参的 start 和 end 还是 指向 0 和 array.length -1int piovt =partition(array,start,end);quick(array,start,piovt -1);quick(array,piovt+1,end);}// 找基准publicstaticintpartition(int[] array,int start,int end){int tmp = array[start];while(start < end){while(start < end && array[end]>= tmp){
end--;}//end 下标就遇到 < tmp 的值
array[start]= array[end];while(start < end && array[start]<= tmp){
start++;}//end 下标就遇到 > tmp 的值
array[end]= array[start];}
array[start]= tmp;// 或 array[end] = tmp;return start;// return end;}
解下来我们 来 看一下 快速排序的 时间复杂度
空间复杂度O(N)
稳定性 ，不稳定发生了跳跃性交换 。
堆排 与 快 排时间复杂度的区别
上面我们 提到了堆排的 时间复杂度 为O( N * log2 N) 而 快排也 是 O(N * log2 N) ,那么 为啥 快排 要 比 堆排 快呢？
堆排序，无论最好还是最坏情况，时间复杂度都是N log2 N。空间复杂度 O(1)*
快排 ， 时间复杂度 最好的情况下O(N * log2 N) 空间复杂度0(N),
其实这里 堆排和快排时间复杂度的连着前面还有 一个 k【K * N log2 N 】，*
只不过快排前面的K要小一点。所以快排要快一点。
两者的使用
在对空间复杂度没有要求的情况： 使用快排
对空间复杂度有要求的情况，或者说对数据的序列也要要求： 堆排
快排的小细节
Hoare 法:完成快排
其实 hoare法 与 挖坑法 很像这里我们 挖坑法找到 了 合适 的值，赋值留下一个坑 ，而 hoare array[start] 找到 大于基准的值 停下，然后，找array[end]小于基准的值，找到了停下，完成交换。然后继续重复上面操作
附上代码
privatestaticintpartition(int[] array,int left,int right){int start = left;int end = right;int pivot = array[left];while(start < end){while(start < end && array[end]>= pivot){
end--;}while(start < end && array[start]<= pivot){
start++;}swap(array, start, end);}// 此时 start 与 end 相遇swap(array, start, left);return i;}
快排优化
上面我们是不是 通过 递归 来完成了 快排，每次递归 我们都需要开辟一个栈帧 ，如果 元素 又几百万上千万，那么大家想一想我们的栈是不是会被挤爆，从而报错，接下来我们就来优化我们的快排，让他不那么因为太多数据而出现栈溢出的现象。
基准值的选择
在优化前我们 先来 基准值的选择
1.选择边上（左或者右）
选择边上这里我们是不是就是挖坑法 或 Hoare 的 方法，通过边上来找基准，
但这种 基准选择可能出先单分支的情况，导致时间复杂度为O(N^2) 如 0 1 2 3 4 5
2.随机选择
3几数取中（例如三数取中）：array[left], array[mid], array[right] 大小是中间的为基准值
附上代码
publicstaticvoidquickSort(int[] array){quick(array,0,array.length-1);}publicstaticvoidquick(int[] array,int start,int end){if(start >= end){return;}// 找基准之前，我们找到中间大小的值 - 使用三数取中法int midValIndex =findmidValIndex(array,start,end);//交换 0 下标 与 中间值 swap(array,start,midValIndex);int piovt =partition(array,start,end);quick(array,start,piovt -1);quick(array,piovt+1,end);}publicstaticint findmidValIndex (int[] array,int start,int end){int mid = start +((end - start)>>>1);// 注意 + 的 优先级 大于 >>> 这里就等价于 （start+ end）/ 2if(array[start]< array[end]){if(array[mid]< array[start]){return start;}elseif(array[mid]> array[end]){return end;}else{return mid;}}else{if(array[mid]> array[start]){return start;}elseif(array[mid]< array[end]){return end;}else{return mid;}}}// 找基准publicstaticintpartition(int[] array,int start,int end){int tmp = array[start];while(start < end){while(start < end && array[end]>= tmp){
end--;}//end 下标就遇到 < tmp 的值
array[start]= array[end];while(start < end && array[start]<= tmp){
start++;}//end 下标就遇到 > tmp 的值
array[end]= array[start];}
array[start]= tmp;// 或 array[end] = tmp;return start;// return end;}
此时 我们 如果 使用 现在的 代码 取 递归 很大的数 就 不会 出现 栈溢出，但是 如果 数字 非常非常大还是 会出现的，因为 递归的程度 过深。
优化总结
- 选择基准值很重要，通常使用几数取中法
- partition 过程中把和基准值相等的数也选择出来
- 待排序区间小于一个阈值时（例如 148），使用直接插入排序
上面我们 总结 过 直接插入排序的一个性质，是不是 数据 越有序 排序 的 越快，那么我们就可以 通过 这个性质来优化快排，我们 给定一个 阀值，
如果 区间（right - left +1） 等于了 阈值那么调用直接插入排序，来排序数据，这样就完成了我们的优化。
附上代码
直接插入排序
publicstaticvoidinserSort(int[] array){int i =0;int j =0;for(i =1;i<array.length;i++){int tmp = array[i];for(j = i -1;j<array.length;j++){if(array[j]> tmp){
array[j+1]= array[j];}else{break;}
array[j+1]= tmp;}}}publicstaticvoidquickSort(int[] array){quick(array,0,array.length-1);}publicstaticvoidquick(int[] array,int start,int end){if(start >= end){return;}// 通过 直接插入排序优化if(end - start +1==148){inserSort(array);return;}// 找基准之前，我们找到中间大小的值 - 使用三数取中法int midValIndex =findmidValIndex(array,start,end);swap(array,start,midValIndex);int piovt =partition(array,start,end);//这里 只能找到 pivot 前面等于 piovt 的值quick(array,start,piovt -1);quick(array,piovt+1,end);}publicstaticint findmidValIndex (int[] array,int start,int end){int mid = start +((end - start)>>>1);// 注意 + 的 优先级 大于 >>> 这里就等价于 （start+ end）/ 2if(array[start]< array[end]){if(array[mid]< array[start]){return start;}elseif(array[mid]> array[end]){return end;}else{return mid;}}else{if(array[mid]> array[start]){return start;}elseif(array[mid]< array[end]){return end;}else{return mid;}}}// 找基准publicstaticintpartition(int[] array,int start,int end){int tmp = array[start];while(start < end){while(start < end && array[end]>= tmp){
end--;}//end 下标就遇到 < tmp 的值
array[start]= array[end];while(start < end && array[start]<= tmp){
start++;}//end 下标就遇到 > tmp 的值
array[end]= array[start];}
array[start]= tmp;// 或 array[end] = tmp;return start;// return end;}
快速排序非递归实现
附上代码
publicstaticvoidquickSort2(int[] array){Stack<Integer> stack =newStack<>();int left =0;int right = array.length -1;int pivot =partition(array,left,right);if(pivot > left +1){// 左边有两个元素或 两个元素以上
stack.push(left);
stack.push(pivot -1);}if(pivot < right -1){// 右边有两个元素 或 两个元素以上
stack.push(pivot +1);
stack.push(right);}while(!stack.isEmpty()){
right = stack.pop();
left = stack.pop();
pivot =partition(array,left,right);if(pivot > left +1){// 左边有两个元素或 两个元素以上
stack.push(left);
stack.push(pivot -1);}if(pivot < right -1){// 右边有两个元素 或 两个元素以上
stack.push(pivot +1);
stack.push(right);}}}
7.归并排序
预备 练习
给你两个有序的数组 合并 成一个有序 的 数组
附上代码
publicstaticint[]mergeArray2(int[] arr1,int[] arr2){if(arr1 ==null&& arr2 !=null){return arr2;}if(arr1 !=null&& arr2 ==null){return arr1;}if(arr1 ==null&& arr2 ==null){returnnull;}int count =0;int[] ret =newint[arr1.length + arr2.length];int s1 =0;int e1 = arr1.length-1;int s2 =0;int e2 = arr2.length-1;while(s1 <= e1 && s2 <= e2){if(arr1[s1]<= arr2[s2]){
ret[count]= arr1[s1];
count++;
s1++;}else{
ret[count]= arr2[s2];
count++;
s2++;}}// 此时说明 有一个数组 拷贝完成while(s1 <= e1){
ret[count]= arr1[s1];
count++;
s1++;}while(s2 <= e2){
ret[count]= arr2[s2];
count++;
s2++;}return ret;}
其实 也可以这样写
publicstaticint[]mergeArray(int[] arr1,int[] arr2){if(arr1 ==null&& arr2 !=null){return arr2;}if(arr1 !=null&& arr2 ==null){return arr1;}if(arr1 ==null&& arr2 ==null){returnnull;}int[] ret =newint[arr1.length + arr2.length];int s1 =0;int e1 = arr1.length-1;int s2 =0;int e2 = arr2.length-1;int count = ret.length;int i =0;while(i < count){if(s1 <= e1 && s2 <= e2 && arr1[s1]<= arr2[s2]){
ret[i]= arr1[s1];
i++;
s1++;}elseif(s1 <= e1 && s2 <= e2 && arr1[s1]>= arr2[s2]){
ret[i]= arr2[s2];
i++;
s2++;}while(s1 > e1 && s2 <= e2){
ret[i]= arr2[s2];
i++;
s2++;}while(s1 <= e1 && s2 > e2){
ret[i]= arr1[s1];
i++;
s1++;}}return ret;}
完成了上面的预备练习，接下来学习我们的归并排序
附上代码
/**
* 归并排序
*/publicstaticvoidmergeSort(int[] array){mergeSortInternal(array,0,array.length -1);}privatestaticvoidmergeSortInternal(int[] array,int low,int high){if(low >= high){return;}// int mid = (low + high) >>> 2;int mid = low +((high - low)>>>1);// 递归 左边mergeSortInternal(array,low,mid);// 递归 右边mergeSortInternal(array,mid+1,high);// 归并merge(array,low,mid,high);}//回忆一下刚刚 写的 合并两个有序的，那么这里合并不就非常简单吗？privatestaticvoidmerge(int[] array,int low,int mid ,int high){// 临时数组大小int[] ret =newint[high - low +1];int s1 = low;int e1 = mid;int s2 = mid +1;int e2 = high;int count =0;// 注意 这里 是 同一个数组while(s1 <= e1 && s2 <= e2){if(array[s1]<= array[s2]){
ret[count]= array[s1];
count++;
s1++;}else{
ret[count]= array[s2];
count++;
s2++;}}// 此时说明 有一个数组 拷贝完成while(s1 <= e1){
ret[count]= array[s1];
count++;
s1++;}while(s2 <= e2){
ret[count]= array[s2];
count++;
s2++;}// 拷贝tmp 数组的元素 放入原来的数组array当中for(int i =0;i<count;i++){// 这里我们 每次加上归并区间的开始，就可 正好完成和并后的拷贝
array[i+low]= ret[i];}}
归并的时间复杂度 ： 这里我们 每一层都需要递归，那么树的高度为 O（log2 N） 每层 为N 那么时间复杂度 为O（N*log2 N）
归并的空间复杂度： O(N)
归并的稳定性 ： 稳定的排序
总结一下我们上面学习的排序，稳定的排序只有 冒泡 插入 归并
归并排序非递归实现
附上代码
//回忆一下刚刚 写的 合并两个有序的，那么这里合并不就非常简单吗？ privatestaticvoidmerge(int[] array,int low,int mid ,int high
// 临时数组大小 int[] ret =newint[high - low +1];int s1 = low;int e1 = mid;int s2 = mid +1;int e2 = high;int count =0;// 注意 这里 是 同一个数组 while(s1 <= e1 && s2 <= e2){if(array[s1]<= array[s2]){
ret[count]= array[s1];
count++;
s1++;}else{
ret[count]= array[s2];
count++;
s2++;}}// 此时说明 有一个数组 拷贝完成 while(s1 <= e1){
ret[count]= array[s1];
count++;
s1++;}while(s2 <= e2){
ret[count]= array[s2];
count++;
s2++;}// 拷贝tmp 数组的元素 放入原来的数组array当中 for(int i =0;i<count;i++){// 这里我们 每次加上归并区间的开始，就可 正好完成和并后的拷贝
array[i+low]= ret[i];}}/**
* 归并排序非递归实现
*/publicstaticvoidmergeSort2(int[] array){int nums =1;// 每组的数据个数 nums 就看作 gap while(nums < array.length){// 数组每次 都需要遍历for(int i =0;i<array.length;i = i + nums *2){int low = i;int mid = low + nums -1;// 这里 需要考虑 mid 和 high 可能 越界if(mid >= array.length){
mid = array.length -1;}int high = mid + nums;if(high >= array.length -1){
high = array.length -1;}// 下标确定后 进行 合并 merge(array,low,mid,high);}
nums *=2;}}
8.海量数据的排序问题
外部排序：排序过程需要在磁盘等外部存储进行的排序
前提：内存只有 1G，需要排序的数据有 100G
因为内存中因为无法把所有数据全部放下，所以需要外部排序，而归并排序是最常用的外部排序
- 先把文件切分成 200 份，每个 512 M
- 分别对 512 M 排序，因为内存已经可以放的下，所以任意排序方式都可以
- 进行 200 路归并，同时对 200 份有序文件做归并过程，最终结果就有序了
9.排序总结
10.其他非基于比较的排序（了解即可）
不用比较大小将数据 变为有序的排序、
1.基数排序
[ 基数排序 | 菜鸟教程]
2.桶排序
这里我们 只需要了解，那么 可以看别人 如何 写 的
桶排序)
3.计数排序
附上代码
/**
* 计数排序
* 时间复杂度 O(N)
* 这里 循环是 并列 的，这里 拿空间 换时间
* 空间复杂度 与 计数的范围有关
* O(M) M :代表当前数据的范围如 900 - 999
* 稳定性: 对当前 这个代码来说 是不稳定 的，但是 本质上 是 稳定的
* 一般适用于 有 n 个数 数据范围 0 - n 之间
*/publicstaticvoidcountingSort(int[] array){int maxVal = array[0];int minVal = array[0];for(int i =0;i<array.length;i++){if(maxVal < array[i]){
maxVal = array[i];}if(minVal > array[i]){
minVal = array[i];}}int[] count =newint[maxVal - minVal +1];for(int i =0;i<array.length;i++){int index = array[i];
count[index - minVal]++;}// 说明 在计数数组当中，已经 把 array数组当中，每个数据出现的次数已经统计好了 // 接下来 ， 只需要，遍历计数数组，把 数组写会 array int indexArray =0;for(int i =0;i<count.length;i++){while(count[i]>0){// 这里一定要加上一个minval 因为不一定i就出现了count[i]
array[indexArray]= i + minVal;
count[i]--;//拷贝一个之后，次数也就少了一个
indexArray++;//下标向后移动 }}}
本文转载自: https://blog.csdn.net/mu_tong_/article/details/125683736
版权归原作者 牧.. 所有， 如有侵权，请联系我们删除。
版权归原作者 牧.. 所有， 如有侵权，请联系我们删除。