概述
常见的排序它们根据时间复杂度、空间复杂度和稳定性等特性适用于不同场景。
算法比较
内部排序：
插入排序：直接插入排序、希尔排序（Shell）
选择排序：简单选择排序、堆排序
交换排序：冒泡排序、快速排序
归并排序：一种有效，稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用
基数排序：属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort
外部排序：
- 使用内存和外部存储结合进行排序
算法代码
冒泡排序
算法步骤：
- 比较相邻的两个元素的大小，如果第一个比第二个大，就交换两个元素的位置
- 对每一个相邻的元素做同样的工作，直至末尾元素为最大
- 去除已排序至末尾的元素，对越来越少的元素数据进行比较、交换，直到没有元素可进行比较
代码实现
/**
* 冒泡排序
* @param arr
*/
public static void bubbleSort(int[] arr){
System.out.println("排序前："+Arrays.toString(arr));
int n = arr.length; //临时变量记录数组剩余排序数量
boolean swapped; //记录是否进行过数据交换
//循环数组剩余数据
for (int i=0; i<n-1; i++){
swapped = false; //初始化交换标识
//对数组中相邻两个数据进行比较、交换（j<n-1-i ：保证交换数据过程中不会越界）
for(int j=0; j<n-1-i; j++){
//两个相邻元素比较，较大的数字后移
if(arr[j] > arr[j+1]){
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
swapped = true; //发生数据交换
}
}
if(!swapped){
break; //无可交换数据，排序完成
}
}
System.out.println("排序后："+Arrays.toString(arr));
}
选择排序
算法步骤：
- 从待排序的元素中选出最小或最大的元素，放置在序列的起始位置
- 出去以排序元素，重新定义序列的起始排序位置，再从剩余序列中找到最小或最大的元素放在当前起始排序位置
- 直到剩余待排序元素为零，排序结束
代码实现
/**
* 选择排序
* @param arr
*/
public static void selectionSort(int[] arr){
System.out.println("排序前："+Arrays.toString(arr));
int len = arr.length; //临时变量，待排序序列长度
for(int i=0; i< len -1; i++){
int index = i; //临时变量，记录起始位置
int tempMin = arr[i]; //临时变量，当前最小值
//循环判断当前数组中的最小数据，并放置在序列起始位置
for (int j=i+1; j<len; j++){
//找到序列中最小的数据
if(tempMin > arr[j]){
//找到小于当前最小值的数据，交换位置
tempMin = arr[j];
index = j;
}
}
//讲最小值放置在arr[i]位置，交换
if(index != i){
arr[index] = arr[i];
arr[i] = tempMin;
}
}
System.out.println("排序后："+Arrays.toString(arr));
}
插入排序
问题：当需要排序的数据较小时，后移判断的次数越多，影响效率
算法步骤：
- 把待排序的元素，看成一个有序表（初始1个元素）和一个无序表（初始N-1个元素）
- 每次从无序表中取出第一个元素，将它跟有序表中的元素依次比较，并将它插入适当的位置，使之成为一个新的有序表
- 直到无序表中无数据，排序完成
/**
* 插入排序
* @param arr
*/
public static void insertSort(int[] arr){
System.out.println("排序前："+ Arrays.toString(arr));
int len = arr.length; //记录数组长度
//int i=1 表示从无序表中的第一个数据开始寻找插入位置
for(int i=1;i<len;i++){
int insertVal = arr[i]; //记录插入元素的值
int insertIndex = i-1; //待插入数据的位置
//查找插入位置，当插入数据位置越界 && 插入数据的值小于前一个数据的值 退出循环
while(insertIndex>=0 && insertVal<arr[insertIndex]){
arr[insertIndex+1] = arr[insertIndex]; //有序表数据放入当前待插入数据的位置
insertIndex--; //索引位置前移
}
arr[insertIndex+1] = insertVal; //将待插入元素的值插入索引位置
}
System.out.println("排序后："+ Arrays.toString(arr));
}
希尔排序
算法步骤：
- 确认初始增量（gap）：通常为数据长度的一半（arr.lengh / 2）或者三分之一加一（arr.lengh / 3 + 1）
- 将数组分为多个子序，每个子序的元素间隔gap，并对每个子序进行插入排序
- 逐渐缩小增量，当增量减小到1时，实际上是对整体数据完成一次直接插入排序，得到最终结果
代码实现
/**
* 希尔排序
* @param arr
*/
public static void shellSort(int[] arr){
System.out.println("排序前："+ Arrays.toString(arr));
int len = arr.length; //记录数组长度
//计算初始增量, 并逐步缩小增量，直至增量 < 1
for(int gap=len/2; gap>0; gap/=2){
//确定增量后，对分组子序做直接插入排序（从后向前移位数据）
for(int i=gap; i<len; i++){
int index = i; //记录移位数据索引
int temp = arr[i]; //待插入数据
//根据计算的步长，逐个数据进行比较
while(index-gap>=0 && temp<arr[index-gap]){
//如果后面的数据小于前面的数据，增移动数据位置
if (arr[index]<arr[index-gap]){
arr[index] = arr[index-gap]; //后向前移动数据
index -= gap;
}
}
arr[index] = temp; //找到插入数据位置
}
}
System.out.println("排序后："+ Arrays.toString(arr));
}
快速排序
对冒泡排序的一个改进，使用分治策略（Divide and Conquer）
应用场景：
算法步骤：
- 选择基准元素，一般为第一个元素或中间元素或最后一个元素
- 分区操作：重新排列数组，将小于基准元素的数据放在基准元素左边，大于基准元素的数据放在元素右边，使用两个指针来记录，找到一个小于基准的元素和一个大于基准的元素时，交换两个元素的位置
- 递归排序：对基准元素的左右两边的子数组递归进行快速排序
代码实现
/**
* 快速排序
* @param arr
*/
public static void quickSort(int[] arr, int low, int high){
if (low < high) {
// 找到中间元素的索引
int pivotIndex = partition(arr, low, high);
// 递归排序基准左侧的元素
quickSort(arr, low, pivotIndex - 1);
// 递归排序基准右侧的元素
quickSort(arr, pivotIndex + 1, high);
}
}
/**
* 分区方法
* @param arr 待分区数组
* @param low 起始索引
* @param high 结束索引
* @return
*/
public static int partition(int[] arr, int low, int high){
int pivot = arr[(low + high)/ 2] ; //取中间值作为支撑点
//确定分区的边界
int lowPtr = low - 1; //小于区域的边界
int highPtr = high + 1; //大于区域的边界
//左侧区域的边界索引 <= 右侧区域的边界索引时，循环找到左右区域符合要求的数据，并且交换位置
while(lowPtr <= highPtr){
//寻找左侧区域大于等于基准元素的数据索引
do{
lowPtr++;
}while (arr[lowPtr] < pivot);
//寻找右侧区域小于等于
do{
highPtr--;
}while (arr[highPtr] > pivot);
//越过边界，则返回基准数据的索引
if(lowPtr >= highPtr){
break; //退出循环，并返回正确的位置
}
//符合要求，交换左右元素位置
int temp = arr[lowPtr];
arr[lowPtr] = arr[highPtr];
arr[highPtr] = temp;
}
return highPtr;
}
归并排序
使用分治策略（Divide and Conquer），归并排序的时间复杂度始终为O(n log n)，因为它总是以最优的方式分割和合并数组。
应用场景：
算法步骤：
- 分解：将待排序数组不断的二等分，直到每个子数组只包含一个元素。
- 解决：递归将每个子数组进行排序
- 合并：将排序好的子数组两两合并，通过比较元素大小，将它们按照顺序组合起来（使用一个临时数组合并元素）
代码实现
/**
* 归并排序
* @param arr
*/
public static void mergeSort(int[] arr, int low, int high){
//将待排序数组不断的进行二等分，直到每个子数组只有一个元素（递归）
if(low < high ){
//对给定数组进行二等分
int mid = (low+high)/2; //中间索引
mergeSort(arr, low, mid); //递归左子数组
// System.out.println();
mergeSort(arr, mid+1, high); //递归右子数组
//合并数组
marge(arr ,low, high, mid);
}
}
/**
* 递归合并数组合并数组
* @param arr
*/
public static void marge(int[] arr,int left,int right, int mid){
//创建临时数组，数组长度为当前子数组的长度
// System.out.println(left+"-"+mid+"-"+right);
int[] temp = new int[right - left + 1]; //临时数组
int l = left; //左子序列索引开始位置
int r = mid + 1; //右子序列索引开始位置
int k = 0; //临时数组索引
//处理左右子序列数据
while (l <= mid && r <=right){
//添加完数据，移动临时数组索引
if(arr[l] <= arr[r]){
//如果左子序列当前元素，小于等于右子序列的当前元素，则将左子序列数据拷贝至临时数组
temp[k++] = arr[l++];
}else{
//如果左子序列当前元素，大于右子序列当前元素，则将右子序列数据拷贝至临时数组
temp[k++] = arr[r++];
}
}
// System.out.println(Arrays.toString(temp));
//处理左子序列剩余数据
while (l<=mid){
temp[k++] = arr[l++];
}
//处理右子序列剩余数据
while (r <=right){
temp[k++] = arr[r++];
}
// System.out.println(Arrays.toString(temp));
//数组拷贝回源数据
k=0;
int tempLeft = left;
while (tempLeft<= right){
arr[tempLeft++] = temp[k++];
}
// System.out.println(Arrays.toString(arr));
}
基数排序
基数排序是一种非比较型整数排序算法，通过逐位分配和收集元素实现排序，典型的以空间换时间逻辑
应用场景：
算法步骤：
- 确定最大位数：找到待排序元素的最大值，确定位数；
- 分配：从最低位开始将元素按当前位值分配到 0~9的桶中；
- 收集：按桶顺序将元素合并回原数组；
- 重复处理：使用分配和收集操作对更高位进行重复处理，直至最高位处理完成；
代码实现
/**
* 基数排序（桶排序）
* @param arr
*/
public static void radixSort(int[] arr){
//确定数据最高位数
int max = arr[0];
for (int tmp : arr){
if(max < tmp){
max = tmp;
}
}
//初始化桶
LinkedList<Integer>[] bucket = new LinkedList[10];
for (int i=0; i<bucket.length; i++){
bucket[i] = new LinkedList<Integer>();
}
//从低位到高位逐位处理
for (int exp = 1; max/exp>0; exp *=10){
//将逐个元素放入桶中
for(int i : arr){
bucket[i / exp %10].add(i);
}
int index = 0;
//收集排序结果
for(int i=0; i<bucket.length; i++){
while (!bucket[i].isEmpty()){
arr[index++] = bucket[i].remove();
}
}
}
}
