一、排序的概念
排序的定义：将一组数据按照特定的顺序重新排列的过程。
排序的目的：是使数据更易于查找、比较和分析。
排序的适应范围：可以应用于各种数据类型。
排序的稳定性：指当出现相同元素时，排序后相同元素的先后顺序保持不变，则称这个排序为稳定排序
内部排序：指在内存中进行排序
外部排序：指借助硬盘完成排序
二、常见排序算法的实现
1、直接插入排序
核心思想：
将数组分为 已排序区间 和 未排序区间 ， 初始情况下，已排序区间就是空，未排序区间就是整个数组，每次从 未排序区间 中选择一个元素，插入到 已排序区间 的合适位置上。
代码实现：
private static void insertSort(int[] arr){
//bound 变量表示边界
//[0,bound) 区间表示有序区间
//[bound，arr.length) 区间是无序区间
for(int bound = 1; bound < arr.length ; bound++ ){
//循环内部进行一次的插入操作
//value 就是无序区间的第一个元素
int value = arr[bound];
//用这个元素在有序区间从后向前比较
int cur = bound - 1;
for(;cur >= 0 ; cur--){
//前一个的值大于bound那么
if(arr[cur] > value){
arr[cur + 1] = arr[cur];
}else {
break;
}
}
//交换元素
arr[cur+1] = value;
}
}特性：元素集合越接近有序，直接插⼊排序算法的时间效率越⾼
时间复杂度：O(n^2)
空间复杂度：O(1);
稳定性：稳定
2、希尔排序
核心思想：
希尔排序是对插入排序的一种优化，引入了 gap（间隔） 的概念，将元素分成多个组，并分别进行插入排序。再不断缩小 gap 直到 gap 为 1 时，就是普通的插入排序。
代码实现：
private static void shellSort(int[] arr){
//计算一个合适的gap值，再不断缩小
int gap = arr.length / 2;
while (gap >= 1){
insertSortGap(arr,gap);
gap /= 2;
}
}
private static void insertSort(int[] arr){
//bound 变量表示边界
//[0,bound) 区间表示有序区间
//[bound，arr.length) 区间是无序区间
for(int bound = 1; bound < arr.length ; bound++ ){
//循环内部进行一次的插入操作
//value 就是无序区间的第一个元素
int value = arr[bound];
//用这个元素在有序区间从后向前比较
int cur = bound - 1;
for(;cur >= 0 ; cur--){
//前一个的值大于bound那么
if(arr[cur] > value){
arr[cur + 1] = arr[cur];
}else {
break;
}
}
//交换元素
arr[cur+1] = value;
}
}希尔排序的时间复杂度不好计算，因为 gap 的取值有很多
3、直接选择排序
核心思想：
将元素划分为 有序区间 和 无序区间，初始情况下 有序区间 为 空 ，每一次遍历都从无序区间里找到最小值，把这个最小值依次放到有序区间
代码实现：
private static void selectSort(int[] arr){
for(int bound = 0;bound < arr.length - 1;bound++){
for (int cur = bound + 1 ; cur < arr.length ; cur++){
if(arr[cur] < arr[bound]){
int temp = arr[cur];
arr[cur] = arr[bound];
arr[bound] = temp;
}
}
}
}时间复杂度：O(N^2)
空间复杂度：O(1)
稳定性：不稳定
4、堆排序
核心思想：
堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一 种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。
代码实现：
private static void selectSort(int[] arr){
for(int bound = 0;bound < arr.length - 1;bound++){
for (int cur = bound + 1 ; cur < arr.length ; cur++){
if(arr[cur] < arr[bound]){
int temp = arr[cur];
arr[cur] = arr[bound];
arr[bound] = temp;
}
}
}
}
private static void headSort(int[] arr){
//1.建堆
createHeap(arr);
int bound = arr.length - 1;
for(int i = 0; i < arr.length ; i++){
//交换堆顶和待排序区间的最后一个元素
int temp = arr[0];
arr[0] = arr[bound];
arr[bound] = temp;
//重新调整堆
//通过 bound 表示堆的元素个数
shiftDown(arr,bound,0);
//最后一个元素归入到 已排序区间
bound--;
}
}
private static void createHeap(int[] arr){
//从最后一个非叶子节点触发，从后往前遍历
for(int i=(arr.length-1-1)/2 ; i >= 0 ; i--){
shiftDown(arr, arr.length, i);
}
}
private static void shiftDown(int[] arr,int length,int index){
int parent = index;
int child = 2 * parent + 1;
while (child < length){
//建立大堆，需要取左右子节点中较大值
if(child + 1 < length && arr[child + 1] > arr[child]){
child += 1;
}
//比较 child 和 parent 元素大小
if(arr[child] > arr[parent]){
int temp = arr[child];
arr[child] = arr[parent];
arr[parent] = temp;
}else{
break;
}
parent = child;
child = 2 * parent + 1;
}
}时间复杂度：O(N*logN)
空间复杂度：O(1)
稳定性：不稳定
5、冒泡排序
核心思想：
通过不断比较相邻元素，一趟过后，最大(最小)的一个元素就会在数组中最末尾的位置，再进行 n - 1 次就可以达到有序
代码实现：
private static void bubbleSort(int[] arr){
for(int bound = 0;bound < arr.length-1 ; bound++){
for (int cur = arr.length - 1 ; cur > bound ; cur--){
if(arr[cur-1] > arr[cur]){
int temp = arr[cur - 1];
arr[cur - 1] = arr[cur];
arr[cur] = temp;
}
}
}
}时间复杂度：O(N^2)
空间复杂度：O(1)
稳定性：稳定
6、快速排序
核心思想：
任取待排序区间中选出某元素作为基准值，按照该排序码将待排序集合分割成两个子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
代码实现：
//此处约定[left,right]闭区间为待处理区间
//快速排序入口
private static void quickSort(int[] arr){
quickSort(arr,0, arr.length-1);
}
//快速排序辅助递归的方法
private static void quickSort(int[] arr,int left,int right){
if(left >= right){
//待处理区间为空或者只有一个元素，无需排序
return;
}
//针对区间进行整理，返回值 index 表示基准值所在的下标
int index = partition(arr,left,right);
//递归左半区间
quickSort(arr,left,index-1);
//递归右半区间
quickSort(arr,index+1,right);
}
private static int partition(int[] arr,int left,int right){
//设定最右侧元素为基准值
int value = arr[right];
//设定两个下标，分别从左往右和右往左
int l = left;
int r = right;
while (l < r){
while (l < r && arr[l] <= value){
l++;
}
while (l < r && arr[r] >= value){
r--;
}
swap(arr,l,r);
}
//循环完成交换重合位置和基准值
swap(arr,l,right);
return l;
}
private static void swap(int[] arr,int i,int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}快速排序在大多数情况下的表现都是非常优秀的，除了个别极端情况会让时间复杂度到O(N^2)
时间复杂度：O(N*logN)
空间复杂度：O(logN)
稳定性：不稳定
7、归并排序
核心思想：
通过递归将待排序的数组分成两个子数组，直到每个子数组只包含一个元素。此时，单个元素的数组自然是有序的。将两个有序的子数组合并成一个有序的数组。合并时，从两个子数组的起始位置开始比较，选择较小的元素放入结果数组中，直到其中一个子数组的所有元素都被合并。然后将另一个子数组的剩余元素直接放入结果数组中。
代码实现：
//归并排序入口方法
private static void mergeSort(int[] arr){
mergeSort(arr,0,arr.length-1);
}
private static void mergeSort(int[] arr,int left,int right){
//如果子区间没有元素或只有一个元素就不再递归
if(left >= right){
return;
}
//把区间分为等长的两个区间，不强制完全相等
int mid = (left + right) / 2;
//递归左半区间
mergeSort(arr,left,mid);
//递归右边区间
mergeSort(arr,mid+1,right);
//递归走到这，说明已经划分为只剩一个元素的有序数组
//将有序数组合并
merge(arr,left,mid,right);
}
private static void merge(int[] arr,int left,int mid,int right){
//创建临时数组保存合并的结果，临时数组的长度应该是 right - left + 1
int[] result = new int[right - left + 1];
//通过判断大小尾插到新数组中
int resultSize = 0;
//两个下标指向每个区间的开头
int cur1 = left;
int cur2 = mid + 1;
while (cur1 <= mid && cur2 <= right){
if(arr[cur1] <= arr[cur2]){
result[resultSize++] = arr[cur1];
cur1++;
}else{
result[resultSize++] = arr[cur2];
cur2++;
}
}
//处理前面奇数划分不均的情况
while (cur1 <= mid){
result[resultSize++] = arr[cur1++];
}
while (cur2 <= right){
result[resultSize++] = arr[cur2++];
}
//把临时数组的结果写回到 arr 的 [left,right] 中
for(int i=0;i<result.length;i++){
arr[left + i] = result[i];
}
}归并排序的思考更多的是解决在磁盘中的外排序问题
时间复杂度：O(N*logN)
空间复杂度：O(N)
稳定性：稳定
三、小结
除了上文提到的这几种，还有许多其他的排序算法，例如 计数排序 ，基数排序 ，桶排序 等等，应该结合实际情况选择使用，学好排序算法的原理可以用这些思想去解决其他的问题。