排序算法
常见的排序算法
快速排序
1.简介
快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较，但这种状况并不常见。事实上，快速排序通常明显比其他 Ο(nlogn) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。
快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。
快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。
快速排序的名字起的是简单粗暴，因为一听到这个名字你就知道它存在的意义，就是快，而且效率高！它是处理大数据最快的排序算法之一了。虽然 Worst Case 的时间复杂度达到了 O(n2)，但是人家就是优秀，在大多数情况下都比平均时间复杂度为 O(n logn) 的排序算法表现要更好。
快速排序的最坏运行情况是 O(n2)，比如说顺序数列的快排。但它的平摊期望时间是 O(nlogn)，且 O(nlogn) 记号中隐含的常数因子很小，比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。
2.思路分析
快速排序算法通过多次比较和交换来实现排序，其排序流程如下：
(1)首先设定一个分界值，通过该分界值将数组分成左右两部分。
(2)将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于分界值，而右边部分中各元素都大于或等于分界值。
(3)然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
(4)重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。
3.图解
3.1 开始
分别从arr数组的两端开始探测。先从右往左找一个小于8的数，再从左往右找一个大于8的数，然后交换他们。这里可以用两个变量L（左边）和R（右边），分别指向序列最左边和最右边。刚开始的时候让L指向数组的最左边，指向数字8。让R指向数组的最右边，指向数字11。
3.2 从右向左遇到小于基准的数
3.3 右边停止，从左向右寻找大于基准的数
3.4 交换L和R相对应的数
交换后
3.5持续上述方法
首先R开始出动。因为此处设置的基准数是最左边的数，所以需要让R先出动，这一点非常重要（请自己想一想为什么）。哨兵R一步一步地向左挪动（即R–-），直到找到一个小于8的数停下来。接下来哨兵L再一步一步向右挪动（即L++），直到找到一个数大于8的数停下来。
交换
交换后
这个时候R继续向左移动
然后L移动
L == R 时候，说明这个位置就是8的位置，交换
得到：
到此第一轮探测结束。此时以基准数8为分界点，8左边的数都小于等于8，8右边的数都大于等于8。回顾一下刚才的过程，其实R的使命就是要找小于基准数的数，而L的使命就是要找大于基准数的数，直到L和R碰头为止。
3.6 处理左边的数
3.7处理右边的数
得到：
4.代码实现
/**
* 快速排序
* @author 尹稳健~
* @version 1.0
* @time 2022/9/10
*/
public class QuickSort {
public static void main(String[] args) {
int[] arr = {8, 12, 19, -1, 45, 0, 14, 4, 11};
quickSort(arr,0,arr.length-1);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i]+" ");
}
}
public static void quickSort(int[] arr,int start, int end){
// 什么时候结束排序？
if (start>end){
return;
}
// 左指针
int L = start;
// 右指针
int R = end;
// 基准
int pivot = arr[start];
// 只要L！=R就继续循环
while (L < R){
// 右边大于基准，从右向左移动
while (L<R && arr[R] >= pivot){
R --;
}
// 左边小于基准，从左向右移动
while (L<R&& arr[L] <= pivot){
L ++;
}
// 说明右边有小于基准的数，左边有大于基准的数，交换
if (L<R){
int temp = arr[L];
arr[L] = arr[R];
arr[R] = temp;
}
}
// L 与 R碰面 找到了 基准的位置
arr[start] = arr[L];
arr[L] = pivot;
// 左边排序
quickSort(arr,start,R-1);
// 右边排序
quickSort(arr,L+1,end);
}
}
快速排序这篇文章写的好，可以参考别人的快速排序写法和理解
归并排序
1.简介
归并排序是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
2.思路分析
归并排序用到了分而治之的思想，其难点是治
- 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
- 首先是分解序列，将序列分解到每个组中序列的数量为1，然后在进行合并排序
- 设定两个指针，最初位置分别为两个已经排序序列的起始位置
- 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
- 重复上一步 直到某一指针达到序列尾
- 将另一序列剩下的所有元素直接复制到合并序列尾
3.图解
3.1 拆分，将所有的序列分解
3.2开始排序合并
每次填充完后，指针移动一位
当左边数组没有元素后，右边直接填充进去
得到
4.代码实现
/**
* 归并排序
* @author 尹稳健~
* @version 1.0
* @time 2022/9/12
*/
public class MergeSort {
public static void main(String[] args) {
int[] arr = {1, 5, 6, 3, 2, 8, 7, 4};
int[] temp = new int[arr.length];
mergeSort(arr,0,arr.length-1,temp);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i]+" ");
}
}
/** 分解,并合并排序 */
public static void mergeSort(int[] arr,int left ,int right,int[] temp){
if (left<right){
//中间索引
int mid = (left+right)/2;
//向左递归分解
mergeSort(arr,left,mid,temp);
//向右递归分解
mergeSort(arr,mid+1,right,temp);
//合并
merge(arr,left,mid,right,temp);
}
}
/**
* 合并排序
* @param arr 未排序的数组
* @param left 左边有序子数组的初始索引
* @param mid 中间索引
* @param right 右边最大索引
* @param temp 临时数组
*/
public static void merge(int[] arr,int left,int mid,int right,int[] temp){
// 左边指针索引
int leftPoint = left;
// 右边指针索引
int rightPoint = mid+1;
// 临时数据的指针
int tempLeft = 0;
// 两个序列都不为空时
while (leftPoint <= mid && rightPoint <= right){
//如果第一个序列的元素小于第二序列的元素，就将其放入temp中
if (arr[leftPoint] <= arr[rightPoint]){
temp[tempLeft] = arr[leftPoint];
leftPoint++;
tempLeft ++;
}else{
temp[tempLeft] = arr[rightPoint];
rightPoint++;
tempLeft ++;
}
}
// 右序列为空，直接将做序列的所有元素填充进去
while (leftPoint <= mid){
temp[tempLeft] = arr[leftPoint];
leftPoint++;
tempLeft++;
}
// 左序列为空，直接将右序列的所有元素填充进去
while (rightPoint <= right){
temp[tempLeft] = arr[rightPoint];
rightPoint++;
tempLeft++;
}
//将临时数组中的元素放回数组arr中
tempLeft = 0;
leftPoint = left;
while (leftPoint <= right){
arr[leftPoint] = temp[tempLeft];
leftPoint++;
tempLeft++;
}
}
}
基数排序
1.简介
基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog?m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。
2.思路分析
- 将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零
- 从最低位开始，依次进行一次排序
- 从最低位排序一直到最高位（个位->十位->百位->…->最高位）排序完成以后, 数列就变成一个有序序列
- 需要我们获得最大数的位数
- 可以通过将最大数变为String类型，再求得它的长度即可
3.图解
首先要有10个桶代表[0-9]
3.1第一轮按个位放入桶中
然后再依次将他们取出，如果一个桶里面有多个元素，先进去的那么先取出来
3.2 第二轮按十位放入桶中
如果没有十位数，那么就在个位的前面补0
3.3第三轮按百位上放入桶中
依次取出后
3.34第四轮按千位放入桶中
取出得到：
4.代码实现
/**
* 基数排序
* @author 尹稳健~
* @version 1.0
* @time 2022/9/13
*/
public class BaseSorted {
public static void main(String[] args) {
int[] arr = {43, 52, 1, 89, 190};
sort(arr);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
public static void sort(int[] arr){
int maxLength = getMaxLength(arr);
// 定义个二维数组桶，存储元素
int[][] bucket = new int[10][arr.length];
// 存储每个桶中有多少个元素
int[] elementCounts = new int[10];
for (int times = 1,step = 1; times < maxLength + 1; times++,step *= 10) {
// 遍历数组，将元素存入桶中
for (int i = 0; i < arr.length; i++) {
// 获取位数上的数
int digits = arr[i] / step % 10;
bucket[digits][elementCounts[digits]] = arr[i];
elementCounts[digits] ++;
}
//将桶中的元素重新放回到数组中
//用于记录应该放入原数组的哪个位置
int index = 0;
for (int i = 0; i < 10; i++) {
// 从桶中按放入顺序依次取出元素，放入原数组
int position = 0;
while ( elementCounts[i] > 0){
arr[index] = bucket[i][position];
position++;
elementCounts[i]--;
index++;
}
}
}
}
/** 获取数组中元素长度最长的长度 */
public static int getMaxLength(int[] arr){
int max = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] > max ){
max = arr[i];
}
}
return (max + "").length();
}
}