前置知识
排序: 按照递增或者递减的顺序把数据排列好
稳定性: 值相等的元素在排序之后前后顺序是否发生了改变
内部排序: 数据放在内存上
外部排序: 数据放在磁盘上
内部排序
基于比较的排序
几大排序算法
1. 堆排序
特点:
思想:
1. 创建大根堆,把所有元素放在大根堆里面
2. 定义变量end,作为最后一个有效元素的下标
3. 交换0下标和end下标的值
4. 进行0下标到end下标的向下调整
5. end--;
这样就可以把大的元素放在后面,从小到大一次按照层序遍历排好
具体代码:
//堆排序private static void creatHeap(int[] array) {for (int parent = (array.length - 1 - 1) / 2; parent >= 0 ; parent--) {siftDown(array,parent,array.length);}}//TODO alt+enterprivate static void siftDown(int[] array,int parent,int length) {int child = 2 * parent + 1;while (child < length) {if(child + 1 < length && array[child] < array[child + 1]) {child++;}if(array[child] > array[parent]) {swap(array,child,parent);parent = child;child = 2*parent+1;}else {break;}}}public static void heapSort(int[] array) {//创建大根堆creatHeap(array);int end = array.length - 1;while (end > 0) {swap(array,0,end);siftDown(array,0,end);end--;}}2. 直接插入排序
特点:
时间复杂度:
最坏情况:O(n^2)
最好情况:O(n) 当数据越有序,排序越快
适用情况: 待排序序列 已经基本上基于有序了
空间复杂度:O(1)
稳定性: 稳定(如果一个排序是稳定的就可以变成不稳定的,但是不稳定的不能变成稳定的)
主要思想:
1. 假设从第一个元素是有序的
2. 从第二个元素开始就一次和前面的元素进行比较,找到合适的位置就插进去.
具体代码:
public static void insertSort(int[] array) {//从第一个元素开始for (int i = 1; i < array.length ; i++) {int j = i - 1;//保存当前下标的值int tem = array[i];//加不加=会对稳定性产生影响,如果一个排序是稳定的就可以变成不稳定的,但是不稳定的不能变成稳定的)for (; j >= 0 ; j--) {//如果前面的元素大于tem,就往前移动if(array[j] > tem) {array[j+1] = array[j];//不用i的原因是j会一直改变,不一定就是j的前一个}else {break;}//最后把元素放在前面//因为循环出来的条件表示必须j要小于0,所以直接传j会下标越界}array[j + 1] = tem;}}3. 希尔排序
特点:
时间复杂度: O(n^0.25)~O(1.6n^0.25)
空间复杂度: O(1)
稳定性: 不稳定
主要思想:
1. 分组,组内进行排序(直接插入排序)
2. 然后逐渐缩小组数
注意:
组数大于1排序都是预排序
缩小增量到最后.然后进行直接插入排序
具体代码:
public static void shellsort(int[] array) {//分组int gap = array.length;while (gap > 0){gap /= 2;//每次分组进行一次直接插入排序shell(array,gap);}}public static void shell(int[] array,int gap) {//我们默认第一个元素是有序的for (int i = gap; i < array.length; i++) {int temp = array[i];//j下标等于i前面一个gap的下标值int j = i - gap;//然后逐渐和该组前面的数进行比较for(; j >= 0 ; j -= gap) {if(array[j] > temp) {//往前移动一个gap的array[j + gap] = array[j];}else {break;}}array[j + gap] = temp;}}4. 选择排序
特点:
时间复杂度:O(n^2)
空间复杂度:O(1)
稳定性:不稳定
主要思想:
1. 俩层循环, 外层循环相当于每一次提供一个比较数,内层循环就把比较数后面的数和比较数进行比较,如果比比较数还小,就记录下来下标的值
2. 内层循环完之后,说明我们找到了这一趟最小值的下标,让其和外层循环所指的元素进行交换.
另一种写法: 双向选择排序
1. 找最大最小值下标,然后放在l和r里面.
2. 交换 l和minIndex下标所指向的值,交换r和maxIndex下标所指向的值
3. l++,r--
不过有个特殊情况:当maxIndex就是i下标的值,会出现问题,如图
具体代码:
法1:
public static void selectSort(int[] array) {for (int i = 0; i < array.length; i++) {int min = i;//让j为i+1for (int j = i + 1; j < array.length; j++) {if(array[min] > array[j]) {min = j;//min保存的是每一趟最小值的下标}}int tmp = array[i];array[i] = array[min];array[min] = tmp;}}法2:
public static void selectSort2(int[] array) {//定义左右下标分别指向第一个和最后一个元素int left = 0;int right = array.length - 1;while (left < right){//定义max和min来记录最大最小值的下标int maxIndex = left;int minIndex = left;for (int i = left; i <= right; i++) {//记录最大最小值的下标if (array[minIndex] > array[i]) {minIndex = i;}if (array[maxIndex] < array[i]) {maxIndex = i;}}//交换值swap(array,left,minIndex);//如果最大值的下标就是left的下标,那么在进行最小值下标交换的的时候,最大值的下标就会改变if(maxIndex == left) {maxIndex = minIndex;}swap(array,right,maxIndex);//改变下标left++;right--;}}5. 冒泡排序
特点:
时间复杂度:O(n^2)
空间复杂度:O(1)
稳定性: 稳定的排序
主要思想:
内层循环每次每次从0开始,把小的交换到前面,大的换到后面,每一轮回,把该轮的最大值换到最后.
优化后:
特点:
时间复杂度:
最好的情况:O(n)
具体思想:
优化:
1. 减少j的遍历次数
2. 考虑极端情况,如果有序的话,我们就直接可以结束循环
具体代码:
未优化版本:
public static void bubbleSort(int[] array) {//i表示趟数for (int i = 0; i < array.length - 1; i++) {//j来比较每个数据的大小for (int j = 0; j < array.length - 1 ; j++) {if(array[j] > array[j + 1]) {swap(array,j,j+1);}}}}优化版本:
public static void bubbleSort1(int[] array) {//i表示趟数for (int i = 0; i < array.length - 1; i++) {boolean flag = false;//j来比较每个数据的大小
// for (int j = 0; j < array.length - 1 - i; j++) {for (int j = 0; j < array.length - 1 - i ; j++) {//优化1if(array[j] > array[j + 1]) {swap(array,j,j+1);flag = true;}}if (flag == false) {break;}}}6. 快速排序(分治思想)
递归:
这几种方法不同主要是在找基准的时候方法不一样
法1 Hoare法
特点:
时间复杂度:
最好情况下:O(nlog2^n)
最坏情况下:O(n^2) 逆序/有序(递归开辟的栈帧太多了,会溢出)
空间复杂度:
最好情况下: O(log2^n)
最坏情况下: O(n) 逆序/有序
稳定性:不稳定
主要思想:
1. 用递归(二叉树前序遍历的思想),不同区间的第一个元素作为基准值
2. 小于基准值的放左边,大于基准值的放右边
法2(挖坑法)
主要思想:
法3 前后指针法
主要思想:
prev指向比基准小的最后一个位置
cur一直去找比基准小的
注意的点:
1. array[right] >= tmp 等于号(不等于可能会死循环,比如首位都是值一样的元素的时候)
2. 为什么从右边开始不从左边开始? 从左边开始一定是遇到比它大的停下来,所以再交换的话,比基准大的数字就换到前面去了
具体代码:(3会1即可),但是思想要明白
Hoare法
public static void quickSort(int[] array) {quick(array,0,array.length - 1);}private static void quick(int[] array, int start, int end) {//走到头了if (start >= end) {return;}//找到基准值//相当于二叉树的前序遍历int pivot = partitionHoare(array,start,end);//调整左区间quick(array,start,pivot - 1);//调整右区间quick(array,pivot + 1,end);}法2(挖坑法)
public static void quickSort1(int[] array) {quick1(array,0,array.length - 1);}private static void quick1(int[] array, int start, int end) {//走到头了if (start >= end) {return;}//找到基准值int pivot = partitionHole(array,start,end);//调整左区间quick(array,start,pivot - 1);//调整右区间quick(array,pivot + 1,end);}//TODO 第二种方法,挖坑法private static int partitionHole(int[] array,int left,int right) {//记录第一个元素的值,把它作为基准int tmp = array[left];int i = left;while (left < right) {while (left < right && array[right] >= tmp) {right--;}//直接把比它小的值填坑即可array[left] = array[right];while (left < right && array[left] <= tmp) {left++;}//直接把比它大的值填坑即可array[right] = array[left];}//相遇的位置就把tmp也填坑array[left] = tmp;//返回基准值的下标return left;}法3 前后指针法
public static void quickSort2(int[] array) {quick2(array,0,array.length - 1);}private static void quick2(int[] array, int start, int end) {//走到头了if (start >= end) {return;}//找到基准值int pivot = partitionIndex(array,start,end);//调整左区间quick(array,start,pivot - 1);//调整右区间quick(array,pivot + 1,end);}//TODO 第三种方法找基准 前后指针法//prev记录比基准小的最后一个位置//cur来找比基准小的数据//三种会一个就可以,建议选前俩种private static int partitionIndex(int[] array, int left, int right) {int prev = left;int cur = left + 1;while (cur <= right) {if (array[cur] < array[left] && array[++prev] != array[cur]) {swap(array, cur, prev);}cur++;}swap(array, prev, left);return prev;}总结:(代码会一种就行,但是三种思想要会)
写选择题,先试2后1再3
1. Hoare
2. 挖坑法
3. 前后指针法
这三种方式 每次划分之后的前后顺序 有可能是不一样的
优化:
1. 主要就是减少递归的次数(均匀的分割,降低树的高度)
法1. 三数取中法(三个数找中位数,分俩个大类,每个类又包含三个子类)
法2. 递归到小的子区间时，可以考虑使用插入排序(我们越递归到后面,区间越小,越有序,那么此时就使用直接插入排序)
具体代码:
public static void quickSort3(int[] array) {quick3(array,0,array.length - 1);}//规定array[mid]<array[left]<array[right],排好序
//求中位数的下标private static int middleNum(int[] array,int left,int right) {int mid = (left + right) / 2;//每次分三种情况来讨论if(array[left] < array[right]) {//mid>rightif(array[mid] > right) {return right;}else if(array[mid] < left) {return left;}else {return mid;}}else {//array[left] > array[right]if(array[mid] < array[right]) {return right;}else if(array[mid] > array[left]) {return left;}else {return mid;}}}private static void quick3(int[] array, int start, int end) {//走到头了if (start >= end) {return;}//TODO 优化2我们越递归到后面,区间越小,越有序,那么此时就使用直接插入排序if(end - start + 1 <= 15) {insertSort(array,start,end);return;}
// System.out.println("start: " + start + "end" + end);//TODO 优化1三数取中法//1 2 3 4 5 6 7//得到中间大的位置int index = middleNum(array,start,end);//把中间大的放在基准位置swap(array,start,index);//4 2 3 1 5 6 7//找到基准值//相当于二叉树的前序遍历int pivot = partitionHoare1(array,start,end);//调整左区间quick(array,start,pivot - 1);//调整右区间quick(array,pivot + 1,end);}private static void insertSort(int[] array, int left, int right) {//从第一个元素开始for (int i = left + 1; i <= right ; i++) {int j = i - 1;//保存当前下标的值int tem = array[i];//加不加=会对稳定性产生影响,如果一个排序是稳定的就可以变成不稳定的,但是不稳定的不能变成稳定的)for (; j >= left ; j--) {//如果前面的元素大于tem,就往前移动if(array[j] > tem) {array[j+1] = array[j];//不用i的原因是j会一直改变,不一定就是j的前一个}else {break;}//最后把元素放在前面//因为循环出来的条件表示必须j要小于0,所以直接传j会下标越界}array[j + 1] = tem;}}非递归:
思路:
使用栈,
通过分割区间调用pivot来进行区间的排序
1. 调用partition方法找到pivot
2. 分别判断左右区间有没有俩个元素(pivot+1和end进行比较,pivot-1和start进行比较)
3. 判断栈空不空,不空就取出俩个元素,建立新的区间->1
具体代码:
public static void quickSortNor(int[] array,int start, int end){Stack<Integer> stack = new Stack<>();//指定start和end的指向start = 0;end = array.length - 1;//找到基准值int pivot = partitonHoare(array,start,end);////判断左右是否有至少俩个元素if(pivot + 1 < end) {//把区间入栈stack.push(array[pivot + 1]);stack.push(end);}if(pivot - 1 > start) {//把区间入栈stack.push(array[start]);stack.push(array[pivot - 1]);}//栈不空就取出俩个元素while (!stack.isEmpty()) {int right = stack.pop();int left = start;pivot = partitonHoare(array,start,end);//判断左右是否有至少俩个元素if(pivot + 1 < end) {//把区间入栈stack.push(array[pivot + 1]);stack.push(end);}if(pivot - 1 > start) {//把区间入栈stack.push(array[start]);stack.push(array[pivot - 1]);}}}
//hoare找基准private static int partitonHoare(int[] array, int left, int right) {int tmp = array[left];int index = left;while (left < right) {//如果左边的值小于基准值while (left < right && array[left] < tmp ) {left++;}//如果右边的值大于基准值while (left < right && array[right] > tmp) {right--;}//此时我们的找到了左边大于基准值的位置,右边小于基准值的位置,我们进行交换swap(array,left,right);}//把基准值放在l = r的位置swap(array,left,index);return left;}
7. 归并排序(分治思想)
递归
特点:
时间复杂度: O(N*log2^N)
空间复杂度: O(n)
稳定性:稳定
主要思想:
先分解再合并(二路归并)
1. 分成一个个子序列,让子序列有序.
2. 然后再合并成,合并后任然保证有序.
具体代码:
public static void mergeSort(int[] array) {mergeFunc(array,0,array.length - 1);}//用来进行分割private static void mergeFunc(int[] array, int start, int end) {//越界就返回if(start >= end) {//不加=会数组越界return;}//找到中间元素int mid = (end + start) / 2;//分割左边mergeFunc(array,start,mid);//分割右边mergeFunc(array,mid + 1,end);//分割到头了,就进行合并merge(array,start,mid,end);}private 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 i = 0;//新数组的下标//创建一个新的数组int[] arryTemp = new int[right - left + 1];//俩端都有元素的时候while (s1 <= e1 && s2 <= e2) {//进行比较if(array[s1] <= array[s2]) {arryTemp[i++] = array[s1++];}else {arryTemp[i++] = array[s2++];}}//此时只有一端有元素,就直接放进数组即可while (s1 <= e1) {arryTemp[i++] = array[s1++];}while (s2 <= e2) {arryTemp[i++] = array[s2++];}//我们要把元素放进原来的数组里面for (int j = 0; j < arryTemp.length; j++) {array[j + left] = arryTemp[j];}}
非递归:
思想:
用gap来确定每个组多少个元素,先一个一个有序,然后俩个俩个有序....
1. gap表示每组有多少个元素
2. 根据gap确定左右半区的边界和中间位置
3. 合并左右半区的元素
具体代码:
private 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 i = 0;//新数组的下标//创建一个新的数组int[] arryTemp = new int[right - left + 1];//俩端都有元素的时候while (s1 <= e1 && s2 <= e2) {//进行比较if(array[s1] <= array[s2]) {arryTemp[i++] = array[s1++];}else {arryTemp[i++] = array[s2++];}}//此时只有一端有元素,就直接放进数组即可while (s1 <= e1) {arryTemp[i++] = array[s1++];}while (s2 <= e2) {arryTemp[i++] = array[s2++];}//我们要把元素放进原来的数组里面for (int j = 0; j < arryTemp.length; j++) {array[j + left] = arryTemp[j];}}//非递归private static void mergeSortNor(int[] array) {//每组多少个数据int gap = 1;while (gap <= array.length) {for (int i = 0; i < array.length; i = i + 2 * gap) {//i每一次循环都在gap个元素的分组下进行排序//确定左右分组的边界值int left = i;int mid = left + gap - 1;int right = mid + gap;//防止越界操作,比如left是数组的最后一个元素,我们Mid和right就越界了if(mid >= array.length) {mid = array.length - 1;}if(right >= array.length) {right = array.length - 1;}//合并左右半区的元素merge(array,left,mid,right);}//增大每组的元素gap *=2;}}
外部排序:
当数据量很大的时候我们需要在磁盘上进行操作.
比如: 内存只有 1 G,需要排序的数据有100G
在内存中放不下这些数据,因此需要外部排序,我们常常用归并排序来进行外部排序
1. 先把文件切分成 200 份，每个 512 M(切割到每份可以被内存放下)
2. 分别对 512 M 排序，因为内存已经可以放的下，所以任意排序方式都可以
3. 进行 2路归并，同时对 200 份有序文件做归并过程，最终结果就有序了
各种基于比较的排序算法的使用场景:
时间和空间复杂度总结:
| 排序方法 | 最好 | 平均 | 最坏 | 空间复杂度 | 稳定性 |
| 冒泡排序 | O(n) | O(n^2) | O(n^2) | O(1) | 稳定 |
| 插入排序 | O(n) | O(n^2) | O(n^2) | O(1) | 稳定 |
| 选择排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 不稳定 |
| 希尔排序 | O(n) | O(n^0.13) | O(n^0.15) | O(1) | 不稳定 |
| 堆排序 | O(n*log(n)) | O(n*log(n)) | O(n*log(n)) | O(1) | 不稳定 |
| 快速排序 | O(n*log(n)) | O(n*log(n)) | O(n^2) | O(logn) ~O(n) | 不稳定 |
| 归并排序 | O(n*log(n)) | O(n*log(n)) | O(n*log(n)) | O(n) | 稳定 |
非基于比较的排序:(量力而行)
1. 计数排序
特点:
时间复杂度:O(max(N,范围))
空间复杂度:O(范围)
稳定性:稳定的
基本思想:
当数据是0-9之间的时候,我们申请一个数组,然后遍历数据,假设我们第一个元素是1,我们就在数组1下标把值+1;
1. 申请一个数组 当前是10
2. 遍历原来的数组,把数字对象的count数组的下标内容进行++
3. 遍历计数数组count 写回原来数组array,此时需要注意写的次数要和元素值一样,最后数组array当中就会存储有序的序列
当数据是90-99之间的时候
len = maxVal - minVal + 1
count[array[i]-minVal]++
具体代码:
https://zhuanlan.zhihu.com/p/26595385?group_id=842495057868226560
public static void countSort(int[] array) {//求最大最小值O(n)int minVal = array[0];int maxVal = array[0];for (int i = 1; i < array.length; i++) {if (array[i] < minVal) {minVal = array[i];}if(array[i] > maxVal) {maxVal = array[i];}}//确定计数数组的长度int len = maxVal - minVal + 1;int[] count = new int[len];//遍历array数组 把数据出现的次数存储到计数数组当中0(n)for (int i = 0; i < array.length; i++) {count[array[i]-minVal]++;}//计数数组已经存放了每个数据出现的次数//遍历计数数组 把实际的数据写回array数组int index = 0;for (int i = 0; i < count.length; i++) {//O(范围)while (count[i] > 0) {array[index] = i + minVal;index++;//写回一次count[i]--;}}}2. 基数排序
主要思想:
1.以个十百位一次依次放入count数组(0-9]
2. 然后依次从0-9对count数组进行底层元素的取出(队列,或者链表(尾插头删))
具体代码
1.10 基数排序 | 菜鸟教程
3. 桶排序
主要思想:
1. 每个桶放不同区间的数
2. 把数据放在桶里面,对桶进行排序
具体代码:
https://blog.csdn.net/qq_27124771/article/details/87651495