文章目录
- 十大排序
- 排序算法复杂度及稳定性分析
- 一、 排序的概念
- 1.排序：
- 2.稳定性：
- 3.内部排序：
- 4.外部排序：
- 二、插入排序
- 1.直接插入排序
- 2.希尔排序
- 三、选择排序
- 1.直接选择排序
- 方法一
- 方法二
- 直接插入排序和直接排序的区别
- 2.堆排序
- 四、交换排序
- 1.冒泡排序
- 2.快速排序
- 1.挖坑法
- 2.Hoare法
- 3.前后指针法
- 4.快速排序的优化
- 方法一：随机选取基准值
- 方法二：三数取中法选基准值
- 方法三：递归到最小区间时、用插入排序
- 5.快速排序非递归实现
- 五、归并排序
- 1.递归实现
- 2.非递归实现
- 3.海量数据的排序问题
- 六、计数排序
- 概念：
- 写法一：
- 写法二：
- 七、桶排序
- 概念
- 代码
- 八、基数排序
- 概念
- 1.LSD排序法（最低位优先法）
- 2.MSD排序法（最高位优先法）
- 基数排序VS基数排序VS桶排序
十大排序
排序算法复杂度及稳定性分析
| 排序方法 | 最好 | 平均 | 最坏 | 空间复杂的 | 稳定性 | 场景 |
|---|---|---|---|---|---|---|
| 冒泡排序 | O(N)(优化情况) | O(N2) | O(N2) | O(1) | 稳定 | 和数据有序无序无关，除非进行优化 |
| 插入排序 | O(N) (有序情况) | O(N2) | O(N2) | O(1) | 稳定 | 趋于有序时使用，把无序插入有序 |
| 选择排序 | O(N2) | O(N2) | O(N2) | O(1) | 不稳定 | 和数据有序无序无关，选一个小的值和前面交换 |
| 希尔排序 | O(N1.3) 局部结果 | O(1) | 不稳定 | 缩小增量分组，最后进行插入排序 | ||
| 堆排序 | O(N*log2N) | O(N*log2N) | O(N*log2N) | O(1) | 不稳定 | 和数据有序无序无关,升序建立大根堆，降序小根堆，堆顶元素和最后元素交换 |
| 快速排序 | O(N*log2N) | O(N*log2N) | O(N2) | O(log2N) ~O（N） | 不稳定 | 数据有序，时间复杂度为O(N2)，O(N*log2N) 最好情况，+优化（三数取中，小区间插入排序） |
| 归并排序 | O(N*log2N) | O(N*log2N) | O(N*log2N) | O（N） | 稳定 | 和数据有序无序无关 |
| 计数排序 | O(N+K) | O(N+K) | O(N+K) | O(N+K) | 稳定 | 非比较，一组集中在某个范围内的数据 |
| 基数排序 | O（NK） | O（NK） | O（NK） | O（N） | 稳定 | 按位分割进行排序，适用于大数据范围排序，打破了计数排序的限制 |
| 桶排序 | O(N+K) | O(N2) | O(N+K) | O(N+K) | 稳定 | 划分多个范围相同的区间，每个子区间自排序，最后合并 |
一、 排序的概念
1.排序：
- 一组数据按递增/递减排序
2.稳定性：
- 待排序的序列中，存在多个相同的关键字，拍完序后，相对次序保持不变，就是稳定的
3.内部排序：
- 数据元素全部放在内存中的排序
4.外部排序：
- 数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序
二、插入排序
1.直接插入排序
和整理扑克牌类似，将乱序的牌，按值的大小，插入整理好的顺序当中
从头开始，比最后一个小的话依次向前挪，直到大于之前牌时，进行插入
1.如果只有一个值，则这个值有序，所以插入排序， i 从下标1开始，把后面的无序值插入到前面的有序当中
2.j = i-1,是i的前一个数，先用tmp将 i位置的值（要插入的值）先存起来，比较tmp和j位置的值
3.如果tmp的值比 j位置的值小，说明要向前插入到有序的值中，把 j位置的值后移，移动到 j+1的位置，覆盖掉 i 的值
4.j 下标向前移动一位，再次和 tmp 比较
5.如果tmp的值比 j 位置的值大，说明找到了要插入的位置就在当前j位置之后，把tmp存的值，放到 j+1的位置
6.如果tmp中存的值比有序的值都小，j位置的值依次向后移动一位，j不停减1，直到排到第一位的数移动到第二位，j的下标从0移动到-1，循环结束，最后将tmp中存的值，存放到 j+1的位置，也就是0下标
public void insertSort(int[] array) {
for (int i = 1; i < array.length; i++) {
int tmp = array[i];//tmp存储i的值
int j = i - 1;
for (; j >= 0; j--) {
if (tmp < array[j]) {
array[j + 1] = array[j];
} else {
// array[j+1] = tmp;
break;
}
}
array[j + 1] = tmp;
}
}
插入就是为了维护前面的有序
-
元素越接近有序，直接插入排序算法的时间效率越高
-
时间复杂度O( N 2 )
-
空间复杂度O ( 1 )
-
稳定性：稳定
如果一个排序是稳定的，可以改变实现为不稳定的
如果是不稳定的排序，则没有办法改变
2.希尔排序
希尔排序shellSort 叫缩小增量排序，是对直接插入排序的优化，先分组，对每组插入排序，让整体逐渐有序
利用了插入排序元素越有序越快的特点
- 先确定一个整数，把待排序数分成多个组，每个组中的数距离相同，
- 对每一组进行排序，然后再次分组排序，减少分组数，组数多，每组数据就少
- 找到分组数=1时，基本有序了，只需要再排一次插入排序即可
一开始组数多，每组数据少，可以保证效率
随着组数的减少，每组数据变多，数据越来越有序，同样保证了效率
到达1分组之前，前面的排序都是预排序
public static void shellSort2(int[] array) {
int gap = array.length;
while (gap > 1) { //gap>1时缩小增量
gap /= 2;//直接在循环内进行最后一次排序
shell(array, gap);
}
}
/**
*
* 希尔排序
* 时间复杂度O(N^1.3---N^1.5)
* @param array
*/
public static void shellSort1(int[] array) {
int gap = array.length;
while (gap > 1) { //gap>1时缩小增量
shell(array, gap);
gap /= 2;//gap==1时不进入循环，再循环为再次排序
}
shell(array, gap);
//组数为1时，进行插入排序
}
public static void shell(int[] arr, int gap) {
//本质上还是插入排序，但是i和j的位置相差为组间距
for (int i = gap ; i < arr.length; i++) {
int tmp = arr[i];
int j = i-gap;
for (; j >=0; j -= gap) {
if (tmp<arr[j]){
arr[j+gap] = arr[j];
}else {
break;
}
}
arr[j+gap] = tmp;
}
}
- 时间复杂度：O( N^1.3 ^) ---- O( N^1.5 ^)
- 空间复杂的：O(1)
- 稳定性：不稳定
三、选择排序
- 在待排序序列中，找到最小值（大）的下标，和排好序的末尾交换，放到待排序列的开头，直到全部待排序元素排完
1.直接选择排序
方法一
/**
* 选择排序
*
* @param array
*/
public static void selectSort(int[] array) {
for (int i = 0; i < array.length; i++) {
int minIndex = i;
for (int j = i + 1; j < array.length; j++) {//找最小值
if (array[j] < array[minIndex]) {
minIndex = j;//只要比minIndex小，放进去
}
}//循环走完后，minIndex存的就是当前未排序的最小值
//将当前i的值和找到的最小值进行交换
swap(array,i,minIndex);
}
}
public static void swap(int[] array, int i, int j) {
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
1.遍历数组长度，i从0开始
2.每次循环，都由minIndex = i 来记录最小值的下标
3.j 从i+1开始遍历，只要比记录的最小值小，就让minIndex记录。找到未排序中的最小值，进行交换
4.如果遍历完后，未排序中没有比minIndex存的值小，i的值就是最小值，i++;
- 效率低, 如果较为有序的序列，在交换时会破坏有序性
- 时间复杂度：O ( N2 )
- 空间复杂的：O ( 1 )
- 稳定性：不稳定
方法二
-
上面的方法，只是先选出最小的值，然后和i的位置交换，
-
进行优化：在遍历时选出最大值和最小值，和收尾进行交换
/**
* 选择排序---选最大值和最小值
*
* @param array
*/
public static void selectSort2(int[] array) {
int left = 0;
int right = array.length - 1;
while (left < right) {
int minIndex = left;
int maxIndex = left;
//选出最大值和最小值
for (int i = left + 1; i <= right; i++) {
if (array[i] > array[maxIndex]) {
maxIndex = i;
}
if (array[i] < array[minIndex]) {
minIndex = i;
}
}
//用最大值和最小值交换首位
swap(array, left, minIndex);
//把left和最小值交换
//如果left恰好就是最大值，就有可能把最大值换到minIndex的位置
if(left == maxIndex){
maxIndex = minIndex;//最大值位置不是left了，而是换到了minIndex
}
swap(array, right, maxIndex);
left++;
right--;
}
}
1.在遍历的过程中，选出最大值的下标和最小值的下标
2.将left和最小值进行交换
3.如果left恰好为最大值，left和最小值交换完成后，最大值就在原来最小值的位置上，
4.maxIndex = minIndex,修正最大值的位置
4.将right和最大值进行交换
直接插入排序和直接排序的区别
- 和插入排序不同的是，插入排序会持续对已排序的数进行比较，把合适的数放在合适的位置
- 直接选择排序就是不断找到最小的值，依次放在排好序的末尾，不干预排好的序列
2.堆排序
- 时间复杂度: O( N * log N)
- 空间复杂的：O (1)
-
升序：建大堆
-
降序：建小堆
-
将一组数据从小到大排序 ——> 建立大根堆
为什么不用小根堆：小根堆只能保证，根比左右小，不能保证左右孩子的大小顺序，并且要求对数组本身进行排序
- 大根堆，保证堆顶元素是最大值，最大值跟最后一个元素交换，将最大的放在最后，usedSize–；
- 向下调整：调整0下标的树，维护大根堆，最大值继续交换到最后一个有效元素的位置
- 从后往前，从大到小依次排列，保证在原来数组本身进行排序
/**
* 堆排序
* 时间复杂度: N*logN
* 空间复杂的：o(1)
*
* @param array
*/
public static void heapSort(int[] array) {
createBigHeap(array);//创建大根堆
int end = array.length-1;
while (end>0){
swap(array,0,end);//堆顶元素和末尾互换
shiftDown(array,0,end);//维护大根堆
end--;
}
}
/**
* 创建大根堆
*
* @param array
*/
public static void createBigHeap(int[] array) {
//最后一个结点的下标 = array.length - 1
//它的父亲结点的下标就为array.length - 1 - 1) / 2
for (int parent = (array.length - 1 - 1) / 2; parent >= 0; parent--) {
shiftDown(array, parent, array.length);
}
}
/**
* 向下调整
*
* @param array
* @param parent
* @param len
*///向下调整，每棵树从父结点向下走
public static void shiftDown(int[] array, int parent, int len) {
int child = parent * 2 + 1;
while (child < len) {
//child < len:最起码要有一个左孩子
if (child + 1 < len && array[child] < array[child + 1]) {
child++;
}//child + 1<len:保证一定有右孩子的情况下，和右孩子比较
//拿到子节点的最大值
if (array[child] > array[parent]) {
swap(array, child, parent);
parent = child;//交换完成后，让parent结点等于等于当前child结点
child = 2 * parent + 1;
//重新求子节点的位置，再次进入循环交换
} else {
break;
//比父结点小，结束循环
}
}
}
- 时间复杂度: O( N * log 2N)
- 空间复杂的：O (1)
- 稳定性：不稳定
四、交换排序
- 根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置
- 将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。
1.冒泡排序
/**
* 冒泡排序
* 时间复杂度 n^2
* 空间复杂度 1
* @param array
*/
public static void bubbleSort(int[]array){
for (int i = 0; i < array.length-1; i++) {//趟数
boolean flg =false;
for (int j = 0; j < array.length-1-i; j++) {
if (array[j]>array[j+1]){
swap(array,j,j+1);
flg = true;
}
}
if (flg == false){
return;
}
}
}
1.遍历 i 代表交换的趟数，遍历 j 进行两两交换
2.j < array.length-1-i 是对于趟数的优化，每走一趟，交换就少一次
3.boolean flg =false;当两两交换时，flg变为true
4.进一步优化：如果遍历完，没发生交换，flg还是false,直接返回，排序结束
- 时间复杂度：O ( N2 )
- 空间复杂度：O ( 1 )
- 稳定性：稳定
2.快速排序
-
时间复杂度：
最好情况：O (N*log2N) ：树的高度为log2N，每一层都是N
最坏情况:O (N2)：有序、逆序的情况下,没有左树，只有右树，单分支树，树的高度是N,每一层都是N
-
空间复杂的：
最好情况：O (log2N)：满二叉树（均匀分割待排序的序列，效率最高）树高为 log2N
最坏情况：O（N）:单分支树,树高为N
-
稳定性：不稳定
-
二叉树结构的交换排序方法
-
任取一个待排序元素作为基准值，把序列一分为二，左子序都比基准值小，右子序都比基准值大，左右两边再重复进行
- 左边找比基准值大的，右边找比基准值小的
1.挖坑法
- 基准值位置挖一个坑，后面找一个比基准值小的把坑埋上
- 前面找一个比基准值大的，埋后面的坑
- 当l==r时，把基准值填入剩下的坑中
- 左右两边重复进行上述步骤，直到排完为止
- 左右两边都以同样的方法进行划分，运用递归来实现
/**
* 快速排序
* 时间复杂度:N*log~2~N
* 空间复杂度
*
* @param array
*/
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;//结束条件
// start == end，说明只剩一个了，是有序的，返回
//start > end ,说明此时的基准值在开头或者末尾
//在开头：start不变，end=pivot-1,start > end ，end=-1 没有左树
//在结尾：end不变，start = pivot+1,start > end,超出索引，没有右树
}
//不断递归quick
int pivot = partition(array, start, end);// 进行排序，划分找到pivot
//然后递归划分法左边，递归划分的右边
quick(array, start, pivot - 1);
quick(array, pivot + 1, end);
}
// ---挖坑法 划分，返回基准值
private static int partition(int[] array, int left, int right) {
int tmp = array[left];//挖一个坑，取left位置为基准值
while (left < right) {
//在右边找一个比基准值小的把坑填上
while (left < right && array[right] >= tmp) {//防止越界
right--;
}
array[left] = array[right];//找到比tmp小的数，填坑,
//在左边找一个比tmp大的值，填到右边的坑
while (left < right && array[left] <= tmp) {//防止越界
left++;
}
array[right] = array[left];
}//如果相遇了，退出循环
array[left] = tmp;//填坑
return left;
}
-
先划分序列，递归左边，然后再递归右边
-
递归结束条件：
start == end时，说明只剩一个了，是有序的，返回
start > end 时 ,说明此时的基准值在开头或者末尾如果基准值在开头：start不变，end=pivot-1,start > end ，end=-1 没有左树
如果基准值在结尾：end不变，start = pivot+1,start > end,超出索引，没有右树
2.Hoare法
- 不同的方法，找出基准值，排的序列是不一样的
- i记录基准值一开始在left位置的下标
- r找到比基准值小的停下来，l找到比基准值大的停下来，互相交换
- l和r相遇的时候，把i 记录基准值的初始下标和相遇位置交换
以左边为基准，先找右边再找左边，相遇的位置就是以右边为基准的值，要比基准小，才能交换
/**
* Hoare法 划分排序找基准值
* @param array
* @param left
* @param right
* @return
*/
private static int partition2(int[] array, int left, int right) {
int tmp = array[left];
int i = left;//记录基准值一开始在left位置的下标
while (left < right) {
while (left < right && array[right] >= tmp) {
right--;
}
while (left < right && array[left] <= tmp) {
left++;
}
swap(array,left,right);
}
swap(array,i,left);
return left;
}
3.前后指针法
- prev记录了比key小的最后一个位置
- cur去找比key值小的，找到后，放到prev的下一个位置
- 最后找到基准值，并且基准值的左边都比它小，右边都比他大
/**
* 前后指针法，划分排序找基准值
*
* @param array
* @param left
* @param right
* @return
*/
private static int partition3(int[] array, int left, int right) {
int prev = left; //prev从left位置开始，left为当前的基准值
int cur = left + 1;//cur在prev的后一个
while (cur <= right) {//遍历完当前数组段
if (array[cur] < array[left] && array[++prev] != array[cur]) {
//只要cur指向的值小于left位置的基准值
//并且prev++后不等于cur的值
swap(array, cur, prev);//将cur和prev位置的值交换
//cur++;
}
//如果cur的值大于基准值,或者prev下一位的值等于cur,cur后移
cur++;
}
//cur越界，循环结束，最后，交换基准值和prev位置的值
//prev记录的就是比基准值小的最后一个数
swap(array, prev, left);
return prev;//prev为基准值
}
4.快速排序的优化
-
时间复杂度：
最好情况：O (N*log2N) ：树的高度为log2N，每一层都是N
最坏情况:O (N2)：有序、逆序的情况下,没有左树，只有右树，单分支树，树的高度是N,每一层都是N
-
空间复杂的：
最好情况：O (log2N)：满二叉树（均匀分割待排序的序列，效率最高）树高为 log2N
最坏情况：O（N）:单分支树,树高为N
-
稳定性：不稳定
-
快速排序有可能发生栈溢出异常，需要进行优化
-
所以要能均匀分割待排序的序列
递归的次数多了，会导致栈溢出，所以优化的方向就是减少递归的次数
在最坏情况下，比如顺序，基准值都取自左边，本身没有左树
方法一：随机选取基准值
看人品，有概率
方法二：三数取中法选基准值
三数：第一个数、中间的数、最后一个数 ，在这三个数中，选出中等值
有可能会变成二分查找 ，避免了出现最坏情况，从中值来比较排序，左右树都有
public static void quickSort(int[] array) {
quick2(array, 0, array.length - 1);
}
private static void quick2(int[] array, int start, int end) {
if (start >= end) {
return;//结束条件
}
//三数取中法
int index = midThree(array, start, end);
//选出的数和开头交换
swap(array,index,start);
int pivot = partition(array, start, end);// 进行排序，划分找到pivot
//然后递归划分法左边，递归划分的右边
quick2(array, start, pivot - 1);
quick2(array, pivot + 1, end);
}
/**
* 三数取中
* @param array
* @param left
* @param right
* @return
*/
private static int midThree(int[] array, int left, int right) {
int mid = (left + right) / 2;
if (array[left] < array[right]) {
if (array[mid] < array[left]) {
return left;
} else if (array[mid] > array[right]) {
return right;
} else {
return mid;
}
} else {
if (array[mid] < array[right]) {
return right;
} else if (array[mid] > array[left]) {
return left;
} else {
return mid;
}
}
}
方法三：递归到最小区间时、用插入排序
进一步优化：减少递归的次数：
-
把快排的递归想象成二叉树，最后两层包含了大部分数，我们要减少这部分的递归
-
前几次的找基准值排序，导致后面几层趋于有序，用直接插入法来排序，进一步提高效率，有点像希尔排序
如果树的高度为h,最后一层就有 2 h-1 个结点 ，后两层占了绝大部分
设置条件：end-start+1 就是当前待排序列的长度，如果小于等于某个较小的值，直接采用插入排序来排剩下的
private static void quick2(int[] array, int start, int end) {
if (start >= end) {
return;//结束条件
}
//优化----减少递归的次数
if(end-start+1<=20){
//如果当前数列的长度，小于=15的时候，
// 用插入排序,然后退出
insertSortQ(array,start,end);
return;
}
//三数取中法
int index = midThree(array, start, end);
swap(array,index,start);
int pivot = partition(array, start, end);// 进行排序，划分找到pivot
//然后递归划分法左边，递归划分的右边
quick2(array, start, pivot - 1);
quick2(array, pivot + 1, end);
}
/**
* 插入排序---来排剩下的待排部分，给定需要的区间
*/
private static void insertSortQ(int[] array,int left,int right) {
for (int i = left+1; i <= right; i++) {
int tmp = array[i];
int j = i - 1;
for (; j >= left; j--) {
if (array[j] > tmp) {
array[j + 1] = array[j];
} else {
break;
}
}
array[j + 1] = tmp;
}
}
5.快速排序非递归实现
- 1.通过使用栈来实现
- 2.每次找到基准值后，把两段序列的开头和末尾压栈
- 3.从栈顶取出两个元素作为新序列的首尾，再次找基准值
- 4.找到基准值后，如果右边有一个元素，不进栈，有两个元素的才能进栈
- 5.pivot< end-1:证明右边有两个元素，pivot>s+1：证明左边有两个元素
- 6.栈为空的时候，排完元素
/**
* 非递归实现快速排序
*
* @param array
*/
public static void quickSortNonRecursive(int[] array) {
Deque<Integer> stack = new LinkedList<>();//利用栈来实现
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);
}
}
}
五、归并排序
- 时间复杂度：O ( N * logzN ) 每一层都是N,有log2N层
- 空间复杂度：O（N），每个区间都会申请内存，最后申请的数组大小和array大小相同
- 稳定性：稳定
目前为止，稳定的排序有：插入、冒泡、归并
- 归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法，采用了分治法
- 将待排序列分解，先使每个子序列有序，再使子序列段间有序
- 将已有序的子序列合并，得到完全有序的序列
- 若将两个有序表合并成一个有序表，称为二路归并
1.递归实现
- 1.确定递归的结束条件，求出中间数mid,
- 2.进行分解，根据mid来确定递归的区间大小
- 3.递归分解完左边，然后递归分解右边
- 4.左右分解完成后，进行合并
- 5.申请新数组进行合并，比较两个数组段，记得查漏补缺
- 6.和并的时候要对齐下标，每个tmp的下标要找到array中对应的下标
/**
* 归并排序
* @param array
*/
public static void mergeSort(int[] array) {
mergeSortFunc(array,0,array.length-1);
}
private 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, right, mid);
}
//进行合并
private static void merge(int[] array, int start, int end, int mid) {
int s1 = start;
int s2 = mid + 1;
int[] tmp = new int[end - start + 1];
int k = 0;//k为tmp数组的下标
while (s1 <= mid && s2 <= end) {//两个数组中都有数据
//进行比较，放到新申请的数组
if (array[s1] <= array[s2]) {
tmp[k++] = array[s1++];
} else {
tmp[k++] = array[s2++];
}
}
//因为有&&条件，数组不一定走完
while (s1 <= mid) {
tmp[k++] = array[s1++];
}
while (s2 <= end) {
tmp[k++] = array[s2++];
}
//此时，将排好的tmp数组的数组，拷贝到array
for (int i = 0; i < tmp.length; i++) {
array[i+start] = tmp[i];//对齐下标
}
}
2.非递归实现
- 1.从1开始分组，先保证每个数都是独立有序的
- 2.进行循环，i下标从0开始，每次跳转组数的两倍
- 3.根据left = i,求出mid和right
- 4.要避免mid和right越界
- 5.分组进行合并
- 6.二倍数扩大组数
/***
* 归并排序，非递归实现
* @param array
*/
public static void mergeSort2(int[] array) {
int gap = 1;
while (gap < array.length) {
//i += gap * 2 i每次跳到下一组
for (int i = 0; i < array.length; i += gap * 2) {
int left = i;
//要避免mid和right越界
int mid = left + gap - 1;
if(mid>=array.length){
mid = array.length-1;//修正越界的情况
}
int right = mid + gap;
if (right>=array.length){//修正越界的情况
right = array.length-1;
}
merge(array,left,right,mid);//进行合并
}
gap *=2;//2倍数扩大组数
}
}
//进行合并
private static void merge(int[] array, int start, int end, int mid) {
int s1 = start;
int s2 = mid + 1;
int[] tmp = new int[end - start + 1];
int k = 0;//k为tmp数组的下标
while (s1 <= mid && s2 <= end) {//两个数组中都有数据
//进行比较，放到新申请的数组
if (array[s1] <= array[s2]) {
tmp[k++] = array[s1++];
} else {
tmp[k++] = array[s2++];
}
}
//因为有&&条件，数组不一定走完
while (s1 <= mid) {
tmp[k++] = array[s1++];
}
while (s2 <= end) {
tmp[k++] = array[s2++];
}
//此时，将排好的tmp数组的数组，拷贝到array
for (int i = 0; i < tmp.length; i++) {
array[i + start] = tmp[i];//对齐下标
}
}
3.海量数据的排序问题
外部排序：排序过程需要在磁盘等外部存储进行的排序
前提：内存只有 1G，需要排序的数据有 100G
因为内存中因为无法把所有数据全部放下，所以需要外部排序，而归并排序是最常用的外部排序
- 先把文件切分成 200 份，每个 512 M
- 分别对 512 M 排序，因为内存已经可以放的下，所以任意排序方式都可以
- 进行 2路归并，同时对 200 份有序文件做归并过程，最终结果就有序了
六、计数排序
- 时间复杂度：
- 空间复杂度：
- 稳定性：稳定
概念：
-
非基于比较的排序
-
计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用
1.统计相同元素出现的个数
2.根据统计的结果将序列回收到原来的序列中
-
计数排序使用的场景：给出指定范围内的数据进行排序
-
使用场景：一组集中在某个范围内的数据
写法一：
- 通过遍历计数数组，循环输出计数数组存的次数
- 1.遍历数组找到最小值最大值
- 2.根据最大最小值，申请一个计数数组
- 3.遍历待排数组进行计数
- 4.遍历计数数组进行输出
/**
* 计数排序
*无法保证稳定
* @param array
*/
public static void countSort2(int[] array) {
//1.遍历数组找到最大值和最小值
int MAX = array[0];
int MIN = array[0];
for (int i = 1; i < array.length; i++) {
if (array[i] > MAX) {
MAX = array[i];
}
if (array[i] < MIN) {
MIN = array[i];
}
}
//2.根据最大最小值，申请一个计数数组
int len = MAX - MIN + 1;//长度
int[] count = new int[len];
//3. 遍历待排数组进行计数
for (int i = 0; i < array.length; i++) {
count[array[i] - MIN]++;
}
//4.遍历计数数组进行输出
int index = 0;//array数组新的下标
for (int i = 0; i < count.length; i++) {
while (count[i] > 0) {
array[index] = i + MIN;//+最小值，求出真正的数
count[i]--;
index++;
}
}
}
写法二：
- 写定数组的大小，用临时数组存储结构
- 计算每个元素在排序后的数组中的最终位置
- 根据计数数组将元素放到临时数组b中，实现排序
- 从后往前，根据原来数组的内容，在计数数组中找到要填写在b数组中的位置，
- 计数数组记录的不再是数字出现是次数，而是应该在数组中存放的位置下标
/**
* 计数排序
*稳定
* @param array
*/
public static void countSort(int[] array) {
int len = array.length;
final int MAX = 256;//常量确定数组大小
int[] c = new int[MAX];//计数数组
int[] b = new int[MAX];//临时数组，存放结果
//统计每个元素的出现次，进行计数
for (int i = 0; i < len; i++) {
c[array[i]]++;// 将a[i]作为索引，对应计数数组c中的位置加1
}
// 计算每个元素在排序后的数组中的最终位置
for (int i = 1; i < MAX; i++) {
c[i] += c[i - 1];// 计数数组中每个元素的值等于它前面所有元素的值之和
}
// 根据计数数组将元素放到临时数组b中，实现排序
for (int i = len - 1; i >= 0; i--) {
b[c[array[i]] - 1] = array[i];// 将a[i]放入临时数组b中的正确位置
c[array[i]]--;// 对应计数数组c中的位置减1，确保相同元素能够放在正确的位置
}
// 将临时数组b中的元素复制回原数组a，完成排序
for (int i = 0; i < len; i++) {
array[i] = b[i];
}
}
七、桶排序
概念
划分多个范围相同的区间，每个子区间自排序，最后合并
-
桶排序是计数排序的扩展版本，计数排序：每个桶只存储单一键值
-
桶排序： 每个桶存储一定范围的数值，确定桶的个数和范围
-
将待排序数组中的元素映射到各个对应的桶中，对每个桶进行排序
-
最后将非空桶中的元素逐个放入原序列中
代码
public static void bucketSort(int[] array){
// 计算最大值与最小值
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for(int i = 0; i < array.length; i++){
max = Math.max(max, array[i]);
min = Math.min(min, array[i]);
}
// 计算桶的数量
int bucketNum = (max - min) / array.length + 1;
ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
for(int i = 0; i < bucketNum; i++){
bucketArr.add(new ArrayList<Integer>());
}
// 将每个元素放入桶
for(int i = 0; i < array.length; i++){
int num = (array[i] - min) / (array.length);
bucketArr.get(num).add(array[i]);
}
// 对每个桶进行排序
for(int i = 0; i < bucketArr.size(); i++){
Collections.sort(bucketArr.get(i));
}
// 将桶中的元素赋值到原序列
int index = 0;
for(int i = 0; i < bucketArr.size(); i++){
for(int j = 0; j < bucketArr.get(i).size(); j++){
array[index++] = bucketArr.get(i).get(j);
}
}
}
八、基数排序
概念
-
基数排序是一种非比较型整数排序算法
-
将整数按位数切割成不同的数字，然后按每个位数分别比较
-
使用场景：按位分割进行排序，适用于大数据范围排序，打破了计数排序的限制
-
稳定性：稳定
-
按位分割技巧：arr[i] / digit % 10，其中digit为10^n。
1.LSD排序法（最低位优先法）
-
从最低位向最高位依次按位进行计数排序。
-
进出的次数和最大值的位数有关
-
桶可以用队列来表示
-
数组的每个元素都是队列
- 1.先遍历找到最大值
- 2.求出最高位
public static void radixSortR(int[] array) {
//10进制数，有10个桶，每个桶最多存array.length个数
int[][] bucket = new int[10][array.length];
//桶里面要存的具体数值
int[] bucketElementCounts = new int[10];
//用来计算，统计每个桶所存的元素的个数，每个桶对应一个元素
//1.求出最大数
int MAX = array[0];
for (int i = 1; i < array.length; i++) {
if (array[i] > MAX) {
MAX = array[i];
}
}
//求最大值的位数，先变成字符串，求字符串长度
int MAXCount = (MAX + "").length();
//最大位数的个数，进行几次计数排序
for (int i = 0; i < MAXCount; i++) {//i代表第几次排序
//放进桶中
for (int k = 0; k < array.length; k++) {
//k相当于遍历待排数值
//array[k] /(int) Math.pow(10, i)%10 求出每次要比较位的数
//求的是个位，并且是对应趟数的个位
int value = (array[k] / (int) Math.pow(10, i)) % 10;
//根据求出的位数，找到对应桶，放到对应桶的位置
bucket[value][bucketElementCounts[value]] = array[k];
//不管value 为多少，bucketElementCounts[value]的值都为0
//相当于存到对应桶的0位bucket[value][0]
bucketElementCounts[value]++; //从0->1
//对应桶的技术数组开始计数
}
//取出每个桶中的元素，赋值给数组
int index = 0;//array新的下标
for (int k = 0; k < bucketElementCounts.length; k++) {//遍历每个桶
if (bucketElementCounts[k] != 0) {//桶里有元素
for (int j = 0; j < bucketElementCounts[k]; j++) {//比那里每个桶的元素
array[index] = bucket[k][j];
index++;
}
}
bucketElementCounts[k] =0;//每个桶遍历完后，清空每个桶的元素；
}
}
}
2.MSD排序法（最高位优先法）
- 从最高位向最低位依次按位进行排序。
- 按位递归分组收集
- 1.查询最大值，获取最高位的基数
- 2.按位分组，存入桶中
- 3.组内元素数量>1,下一位递归分组
- 4.组内元素数量=1.收集元素
/**
* 基数排序--MSD--递归
* @param array
*/
public static void radixSortMSD(int[] array) {
//1.求出最大数
int MAX = array[0];
for (int i = 1; i < array.length; i++) {
if (array[i] > MAX) {
MAX = array[i];
}
}
//求最大值的位数，先变成字符串，求字符串长度
int MAXCount = (MAX + "").length();
// 计算最大值的基数
int radix = new Double(Math.pow(10, MAXCount - 1)).intValue();
int[] arr = msdSort(array, radix);
System.out.println(Arrays.toString(arr));
}
public static int[] msdSort(int[] arr, int radix){
// 递归分组到个位，退出
if (radix <= 0) {
return arr;
}
// 分组计数器
int[] groupCounter = new int[10];
// 分组桶
int[][] groupBucket = new int[10][arr.length];
for (int i = 0; i < arr.length; i++) {
// 找分组桶位置
int position = arr[i] / radix % 10;
// 将元素存入分组
groupBucket[position][groupCounter[position]] = arr[i];
// 当前分组计数加1
groupCounter[position]++;
}
int index = 0;
int[] sortArr = new int[arr.length];
// 遍历分组计数器
for (int i = 0; i < groupCounter.length; i++) {
// 组内元素数量>1，递归分组
if (groupCounter[i] > 1) {
int[] copyArr = Arrays.copyOf(groupBucket[i], groupCounter[i]);
// 递归分组
int[] tmp = msdSort(copyArr, radix / 10);
// 收集递归分组后的元素
for (int j = 0; j < tmp.length; j++) {
sortArr[index++] = tmp[j];
}
} else if (groupCounter[i] == 1) {
// 收集组内元素数量=1的元素
sortArr[index++] = groupBucket[i][0];
}
}
return sortArr;
}
基数排序VS基数排序VS桶排序
-
都是非比较型排序
-
三种排序算法都利用了桶的概念
1.计数排序：每个桶只存储单一键值；
2.基数排序：根据键值的每位数字来分配桶
3.桶排序： 每个桶存储一定范围的数值；
点击移步博客主页，欢迎光临~
