//排序前,这里的5a和5b都是5，只是为了方便区分
arr[9,5a,2,7,3,6,4,5b,8,0]
//排序后
//稳定的排序算法
arr1[0,2,3,4,5a,5b,6,7,8,9]
//不稳定的排序算法
arr2[0,2,3,4,5b,5a,6,7,8,9]
什么时候需要用到稳定性的排序算法呢？
要排序的内容是一个复杂对象的多个数字属性，且原本的初始顺序存在意义，那么若我们需要在二次排序的基础上，保持原因的排序，需要使用稳定性的排序算法
例如：
要排序的内容是一组原本按照价格（price）从高到低的商品对象，如今再按照商品的销量进行排序，使用稳定性的排序算法，可以得到销量相同的对象仍然保持其价格按照原有的高低进行排列，只有销量不同时才会按照销量排序
内部排序
：数据元素全部放在内存中的排序。
外部排序
：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。
1.2 常见的排序算法
常见的排序算法
| 1. 插入排序 |
1.1直接插入排序 |
|
1.2希尔排序 |
| 2.选择排序 |
2.1选择排序 |
|
2.2堆排序 |
| 3.交换排序 |
3.1冒泡排序 |
|
3.2快速排序 |
| 4.归并排序 |
4.1归并排序 |
2. 常见排序算法的实现
2.1 基于选择的思想
每次从无序区间中选择最小/最大值，放在无序区间的最开始或者最后面，直到整个数组有序
2.1.1 直接选择排序
在整个无序区间中选择最小值放在无序区间的最开始。
每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。
//选择排序--直接选择排序
public static void selectSort(int[] array){
// 外层循环表示需要走的内层循环趟数
// 每走一次内层循环，就有一个元素(当前最小值)放在正确位置
for(int i = 0; i< array.length-1; i++){
int min = i;
for(int j = i + 1;j < array.length;j++){
if(array[min] > array[j]){
min = j;
}
}
// 此时min就保存了最小值索引，交换i和min的元素即可
swap(array,i,min);
}
}
直接选择排序的特性总结
1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：不稳定
2.1.2 堆排序
堆排序
(Heapsort)
是指利用堆这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。
需要注意的是排升序要建大堆，排降序建小堆
。
最大堆的堆顶是堆中最大元素，每次都将堆顶元素和数组最后一个元素进行交换，然后进行堆的shfitDown操作，将数组内除最后一个元素（最大值）以外的数变为最大堆，然后重复操作即可得到一个升序排列
降序排列只需要使用最小堆进行上述操作即可
//选择排序--堆排序，升序
public static void heapSort(int[] array){
//从最后一个非叶子节点开始执行下沉操作,将数组变为最大堆
for(int i = (array.length-1-1) >> 1; i>= 0; i--){
shiftDown(array,i,array.length);
}
//不断交换最后一个堆顶元素和数组的最后一个位置
for(int i = array.length-1; i>0; i--){
swap(array,i,0);
shiftDown(array,0,i);
}
}
private static void shiftDown(int[] array, int i, int size) {
while(2*i+1<size){
int j = 2*i+1;
if(j+1 < size && array[j+1] > array [j]){
j = j+1;
}
if(array[j] < array[i]){
break;
}else{
swap(array,j,i);
i = j;
}
}
}
直接选择排序的特性总结
1. 堆排序使用堆来选数，效率就高了很多。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(1)
4. 稳定性：不稳定
2.2 基于插入的思想
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。实际中我们玩扑克牌时，就用了插入排序的思想
2.2.1 直接插入排序
当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与array[i- 1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移
// 直接插入排序
public static void insertSort(int[] array){
//这里的i=1从第二个元素开始遍历，因为第一个元素已经是有序的
for(int i = 1; i <array.length; i++){
//向前对比，因为前面是有序空间，如果比前面小，则两两交换
for(int j = i; j >= 1 && array[j] < array[j-1]; j--){
swap(array,j,j-1);
}
}
}
当数组近乎有序的前提下：直接插入排序的时间复杂度为O(N),因此插入排序经常作为其他高阶排序的辅助优化手段
当待排序的区间很小，试验论证（16个元素以内，JDK中是64个元素之内的数组近乎都可以认为是近乎有序数组），直接使用插入排序进行排序即可。
直接插入排序的特性总结
1. 元素集合越接近有序，直接插入排序算法的时间效率越高
2. 时间复杂度：O(N^2)，但在近乎有序的数组上，时间复杂度为接近O(N)
3. 空间复杂度：O(1)，它是一种稳定的排序算法
4. 稳定性：稳定
2.2.2 希尔排序（缩小增量排序）
希尔排序是对直接插入排序的优化：插入排序在近乎有序的数组上性能非常好，因此，能否有个方法，先将数组调整的近乎有序，然后使用插入排序呢？
由此我们引申出了希尔排序
宏观思路，先将数组调整的近乎有序，最终在整个近乎有序的数组上来一次插入排序
1.先选定一个整数Gap, 将待排序的集合按照Gap分组（所有距离为Gap的元素在同一组，比如gap=2,下标为0的元素就和下标为2的元素为同一组，当然下标4,6,8...都是一组，1,3,5...是一组）
2.对同一组的元素进行排序，不断缩小这个Gap的长度，（gap/2或者gap/3）
3.重复上述过程直到Gap==1时停止，此时的整个数组已经近乎有序，最终再来一次全数组的插入排序，整个集合就有序了
// 希尔排序
public static void shellSort(int[] array){
//让gap取值为数组长度/2
int gap = array.length >> 1;
//当gap != 1时，都是在分组进行排序
while(gap > 1){
insertSortByGap(array,gap);
gap = gap >> 1;
}
//当gap == 1时，整个数组已经近乎有序，整体来一次插入排序即可
insertSort(array);
}
//分组后在组内进行排序
private static void insertSortByGap(int[] array, int gap) {
//往后遍历--外层循环，往前对比元素是否需要交换位置--内层循环
for(int i = gap; i < array.length; i++){
//向前看
for(int j = i; j -gap >= 0 && array[j] < array[j-gap]; j -= gap ){
swap(array,j,j-gap);
}
}
}
上面的insertsortByGap方法中，如果把gap替换成1，则和插入排序一模一样！
希尔排序的特性总结：
1. 希尔排序是对直接插入排序的优化。
2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，再使用插入排序就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排序的时间复杂度都不固定
4. 稳定性：不稳定
2.3基于归并的思想
2.3.1归并排序
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
归并排序将待排序的数组划分为以下两个阶段：
阶段一：归而为一
不管三七二十一，不断将数组一分为二，直到每个子数组只剩下一个元素，拆分阶段结束（此时每个子数组都是有序数组）
[10,6,7,1] --> [10,6] [7,1] --> [10] [6] [7] [1]
阶段二：并而为整
不断的将相邻的两个有序子数组合并为一个大的有序数组，直到合并为完整的数组，此时整个数组有序！归并排序的核心就是merge函数（合并过程）！
[10] [6] [7] [1] --> [6,10] [1,7] --> [1,6,7,10]
1.先创建一个大小为r-l+1的临时数组aux
2.将两个子数组的所有内容复制到aux中
3.进行两个子数的比较合并过程，直到两个子数组合并完成
//归并排序
public static void mergeSort(int[] arr){
//传入原数组和头尾的下标
mergeSortInternal(arr,0,arr.length-1);
}
//在数组arr[l....r]之间进行归并排序
private static void mergeSortInternal(int[] arr, int l, int r) {
//base case,当l >= r时，数组内只剩下最后一个元素，或者没有元素了
if(l >= r){
return;
}
int mid = l + ((r-l)>>1);
//现在左半数组arr[l...mid]上进行归并排序
mergeSortInternal(arr,l,mid);
//继续在右半数组arr[mid+1,r]上进行归并排序
mergeSortInternal(arr,mid+1,r);
//如果此时arr[mid] <= arr[mid+1]
//则说明，左子数组的最大值小于等于右子数组的最小值，此时大数组已经有序，不需要合并
//开始合并两个有序的子数组
if(arr[mid] > arr[mid+1]){
merge(arr,l,mid,r);
}
}
//合并arr[l..mid]和arr[mid+1,r]两个子数组合并为一个有序数组
private static void merge(int[] arr, int l, int mid, int r) {
//先创建一个大小为两个子数组之和的临时数组aux
int[] aux = new int[r-l+1];
//复制两个子数组内容到aux之中
//原数组名称arr,原数组起始索引l,新数组名称aux,新数组起始索引0，拷贝的长度r-l+1
System.arraycopy(arr,l,aux,0,r-l+1);
int i = l, j = mid+1;
for(int k = l; k <= r; k++){
if(i > mid){
//此时左边子数组已经覆盖完毕，直接将右边子数组剩下的所有内容覆盖
arr[k] = aux[j-l];
j++;
}else if(j > r){
//此时右边子数组已经覆盖完毕，直接将左边子数组剩下的所有内容覆盖
arr[k] = aux[i-l];
i++;
}else if(aux[i-l] <= aux[j-l]){
//两个子数组都有元素，且左子数组的元素小于等于右子数组元素
arr[k] = aux[i-l];
i++;
}else{
//右子数组的元素小于左子数组的元素
arr[k] = aux[j-l];
j++;
}
}
}
归并排序用于海量数据处理（数据规模大到内存放不下，需要借助外存）
eg: 内存只有1G，需要排序的数据有100个G
a. 先将待排序的数据划分为200份，每份0.5G
b. 分别将每份数据加载到内存中进行任意排序方法对其排序
c. 进行200份有序文件的合并过程，最终达到整体数据有序 merge
归并排序的特性总结
1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(N)
4. 稳定性：稳定
2.4基于交换的思想
基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。
2.4.1 冒泡排序
当数组中前一个元素大于后一个元素，交换，使得较小的元素移动到前面，较大的移动到后面，重复对比和交换的过程，我们称之为冒泡排序
//冒泡排序
public static void bubbleSort(int[] array){
for(int i = 0; i < array.length-1; i++ ){
for(int j = 0 ; j < array.length-1-i; j++){
if(array[j] > array[j+1]){
swap(array,j,j+1);
}
}
}
}
冒泡排序的特性总结
1. 冒泡排序是一种非常容易理解的排序
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：稳定
2.4.2 快速排序
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元 素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
快速排序的核心在于分区函数的实现：针对分区函数的实现，有N种操作
例如：Hoare版分区方法
1.默认数组第一个元素或者最后一个元素作为分区点v，其中i索引指向数组开始的位置，j索引指向终止的位置
2.先让j从后向前扫描碰到第一个 < v的值停止，然后再让i从前向后扫描，碰到第一个＞v的值停止，交换i和j对应的值，不断重复，直到i>=j时停止
3.最后再交换交换v和j对应的值
4.此时j的左侧全部是小于分区点的值，右侧全部是大于分区点的值，在这两个子区间继续上述过程，直到整个数组有序
准备实现的分区方法：挖坑法（针对hoare法的一个改进版本）
arr[4,5,2,7,3,6,8,9]
//分区点v == 4，此时就把数组中4的位置给空出来形成一个坑位
//让i索引指向起始位置，j指向终点位置,?表示坑位，没有任何元素
arr[?,5,2,7,3,6,8,9]
//让j从右向左扫描碰到第一个比v小的值和i交换
arr[3,5,2,7,?,6,8,9]
//让i从右向左扫描碰到第一个比v大的值和j交换
arr[3,?,2,7,5,6,8,9]
//重复过程直到i>=j
arr[3,2,?,7,5,6,8,9]
//最后把4填入坑位？中
arr[3,2,4,7,5,6,8,9]
快速排序挖坑法
//快速排序
public static void quickSort(int[] array){
quickSortInternalByHole(array,0,array.length-1);
}
private static void quickSortInternalByHole(int[] array, int l, int r) {
//base case
if(l >= r){
return;
}
//设置分区点的索引
int pivot = partitionByHole(array,l,r);
//在左半区间和右半区间进行快排
quickSortInternalByHole(array,l,pivot-1);
quickSortInternalByHole(array,pivot+1,r);
}
//基于挖坑法实现的函数
private static int partitionByHole(int[] array, int l, int r) {
//默认分区点为数组首元素
int v = array[l];
int i = l;
int j = r;
while(i<j){
//一定要先从后向前扫描，碰到第一个小于v的元素停止
while(i<j && array[j] >= v){
j--;
}
//此时j指向第一个小于v的元素,填坑，填坑之后j对应的元素空出位置
array[i] = array[j];
//i继续从前向后扫描
while(i<j && array[i] <= v){
i++;
}
array[j] = array[i];
}
//当这个循环退出的时候，说明i和j重合，填充分区点
array[j] = v;
return j;
}
特殊情况：
上面的代码中，当待排序的集合近乎有序时，快速排序会退化为O(N^2)的时间复杂度
问题就出在分区点的选择上，因为上述代码分区点选择的是数组首元素，在待排序的集合近乎有序时，分区的logn二叉树就退化成了单枝数，此时时间复杂度就发生了退化
解决方案：
随机在数组中选择一个数作为分区点
快速排序总结
1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(logN)
4. 稳定性：不稳定 （快速排序是否稳定要看分区函数的具体实现，由于分区函数众多，不能保证都有稳定性，因此总体而言是不稳定的）
