一.排序的概念及引用： 1.排序的概念： 所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。 2.稳定性 ：假定在待排序的记录序列中， 存在多个具有相同的关键字的记录 ，若 经过排序 ，这些 记录的相对次序保持不变 ，即在 原序列中，r[i]=r[j]，排序前r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的 内部排序 ：数据元素全部放在内存中的排序。 外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。 3.常见的排序算法：
二. 常见排序算法的实现(这里默认升序排列)：
1 插入排序 ：
大概思路：就是把待排序的记录按其关键码值的大小 逐个插入到一个已经排好序的有序序列中 ， 直到所有的记录插入完为止，得到一个新的有序序列 。实际中我们玩扑克牌时，就用了插入排序的思想。
具体思路：定义一个 i, 一个 j , j = i-1 , 把array[i]放入tmp变量 ，让tmp和 array[j]比较，大的就往后放。
如下：
代码：
代码语言：javascript复制/**插入排序
* 时间复杂度：O (N^2)
* 空间复杂度：O (1)
* 稳定性：插入排序本身就是一个稳定的排序
* 数据本书有序时 ，时间复杂度：O (N)
* @param array
*/
public static void insetSort(int[] array) {
for (int i = 1; i < array.length; i ) {
int tmp = array[i];
int j = i-1;
for (; j >= 0; j--) {
if (tmp > array[j]) {
array[j 1] = tmp;
break;//tmp为空 i ，因此跳出去第一层
}else {
array[j 1] = array[j];
}
}
//当j等于负数时,或者跳出来时
array[j 1] = tmp;
}
}直接插入排序的特性总结：
(1). 元素集合越接近有序，直接插入排序算法的时间效率越高
(2). 时间复杂度：O(N^2)
(3). 空间复杂度：O(1)，它是一种稳定的排序算法
(4). 稳定性：稳定
2.希尔排序 ( 缩小增量排序 )：
希尔排序法又称缩小增量法 。希尔排序法的基本思想是： 先选定一个整数，把待排序文件中所有记录分成多个组，
所有 距离为gap 的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达 gap=1 时，所有记录在统一组内排好序 。
希尔排序也算是插入的优化
希尔排序的特性总结：
1. 希尔排序是对直接插入排序的优化。
2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很 快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排序的时间复杂度都不固定，
时间复杂度可以记住O(N^1.3 - N^1.5).
空间复杂度：O(1)
稳定性：稳定
图解：
代码：
代码语言：javascript复制/**时间复杂度：O (n^1.3 - n^1.5)
* 空间复杂度O (1)
* 希尔排序：把数据跳跃式的分为，gap组，进行插入排序，最后会变成一组进行插入排序，这个时候已经基本不上基于有序
*/
public static void shellSort(int[] array){
int gap = array.length;
while (gap > 1) {
gap /= 2;
shell(array,gap);
}
}
public static void shell(int[] array, int gap){
for (int i = 1; i < array.length; i ) {
int tmp = array[i];
int j = i-gap;
for (; j >= 0; j -= gap) {
if (tmp > array[j]) {
array[j gap] = tmp;
break;//tmp为空 i ，因此跳出去第一层
}else {
array[j gap] = array[j];
}
}
//当j等于负数时,或者跳出来时
array[j gap] = tmp;
}
}2.选择排序：
1.直接选择排序：
从每一次从待排序的数据元素中选出最小（或最大）的一个元素，然后跟新下标，大的往后拿，小的往前放，直到全部待排序的数据元素排完 。
如图：
直接选择排序的特性总结：
1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：不稳定
代码：这里给出两种写法：
代码语言：javascript复制 /**
* 选择排序:写法一
* 时间复杂度 O (N^2)
* 空间复杂度：O (1)
* 稳定性：不稳定
*/
public static void selectSort(int[] array) {
for (int i = 0; i < array.length; i ) {
int mixIndex = i;
for (int j = i 1; j < array.length; j ) {
if (array[mixIndex] > array[j]) {
mixIndex = j;
}
}
//遍历完一趟就，把后面找到的比较小的值和前面交换
swap(array,i,mixIndex);
}
}
private static void swap(int[] array, int i, int j) {
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
/**选择排序:写法二
* 时间复杂度 O (N^2)
* 空间复杂度：O (1)
* @return
*/
public static void selectSort1(int[] array) {
int left = 0;
int right = array.length-1;
while (left < right) {
int maxIndex = left;
int mixIndex = left;
for (int i = left 1; i <= right; i ) {
if (array[maxIndex] < array[i]) {
maxIndex = i;//更新下标
}
if (array[mixIndex] > array[i]) {
mixIndex = i;//更新下标
}
}
//最大值换到右边，最小值换到左边
swap(array,left,mixIndex);
//如果是最大值刚好是left下标，最大值被换到了最小值的位置，这个时候就要maxIndex = mixIndex;
if (left == maxIndex) {
maxIndex = mixIndex;
}
swap(array,right,maxIndex);
left ;
right--;
}
}2.堆排序：
堆排序(Heapsort) 是 指利用堆积树（堆）这种数据结构 所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是 排升序要建大堆，排降序建小堆 。
还有一个这里如果忘记了可以回顾一下： 对优先级队列(堆)的理解-CSDN博客
具体思路： 首先要建堆（这里我们建立大根堆，采用向下建堆，效率很高） 其次要交换
交换是，最后一棵树的叶子节点与整棵树的根节点交换， 最后也要调整为满足大根堆的
完全二叉树。
图解：
代码：
代码语言：javascript复制/**堆排序
*时间复杂度：O(n n*log^n) == O(n*log^n)
* 空间复杂度：O(1)
* 稳定性：不稳定
*/
public static void heapSort(int[] array) {
//1.建堆
crateHeap(array);//n
//开始堆排序
int end = array.length-1;//找到最后一棵树的叶子节点
while (end > 0) {//n
swap(array,0,end);//交换，最后一棵树的叶子节点和整棵树的根
siftDown(array,0,end);//调整，从0位置开始// log^n
end--;
}
}
//向下建堆
private static void crateHeap(int[] array) {
for (int parent = (array.length-1-1)/2; parent >= 0; parent--) {
siftDown(array,parent,array.length);
}
}
/**
* @param array
* @param parent:每颗子树开始调整的根节点
* @param length:每颗子树开始调整的结束节点
*/
private static void siftDown(int[] array, int parent, int length) {
int child = parent*2 1;
//找左右最大的孩子
while (child < length) {
if (child 1 < length && array[child 1] > array[child]) {
child ;
}
if (array[child] > array[parent]) {
swap(array,child,parent);
//更新
parent = child;
child = parent*2 1;
}else {
break;
}
}
}直接选择排序的特性总结：
1. 堆排序使用堆来选数，效率就高了很多。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(1)
4. 稳定性：不稳定
3 交换排序 ： 基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。 1 冒泡排序 ： 冒泡排序就是一趟一趟的来，然后趟数越来越少。 图解： s
代码：
代码语言：javascript复制
/**冒泡排序：(讨论没有优化过的——>没有下面的，flg，) O(N^2)
* 优化后可能达到：O(N)
*
* 空间复杂度：0(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) {
break;
}
}
}冒泡排序的特性总结： 1. 冒泡排序是一种非常容易理解的排序 2. 时间复杂度：O(N^2) 3. 空间复杂度：O(1) 4. 稳定性：稳定
2.快速排序 ：
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为： 任取待排序元素序列中的某元 素作为基准值，按照该排序码 将待排序集合分割成两子序列 ， 左子序列中所有元素均小于基准值 ， 右子序列中所有元素均大于基准值 ， 然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
图解： 这里图解是 Hoare版：（挖坑法和Hoare 版也从差不多）
在左右子序列越来越有序时，整个序列也越来越有序，递归层次也会减少 ，这个时候我们可以从某个位置开始插入排序，这样效率将大大提高，
这里我们给出（递归优化后写法和非递归写法）
代码语言：javascript复制 //递归写法-》快速排序：
public static void quickSort(int[] array) {
quick(array,0,array.length-1);
}
public static void quick(int[] array,int start,int end) {
//递归结束条件
if (start >= end) {
return;
}
//优化->减少递归层次,在某个越来越有序的情况下，用插入排序
if (end - start 1 <= 10) {
insetSortRange(array,start,end);
return;
}
//优化.->在排序之前找到中位数，h和left下标交换,达到均匀分配数组元素的目的
int midIndex = getMiddleNum(array,start,end);
swap(array,start,midIndex);
//先划分数组
int pivot = partition(array,start,end);
//递归,划分后数组
quick(array,start,pivot-1);
quick(array,pivot 1,end);
}
//某个位置开始插入排序
private static void insetSortRange(int[] array, int start, int end) {
for (int i = start 1; i <= end; i ) {
int tmp = array[i];
int j = i-1;
for (; j >= start; j--) {
if (tmp > array[j]) {
array[j 1] = tmp;
break;//tmp为空 i ，因此跳出去第一层
}else {
array[j 1] = array[j];
}
}
//当j等于负数时,或者跳出来时
array[j 1] = tmp;
}
}
//找中位数
private static int getMiddleNum(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[left]) {
return left;
} else if (array[mid] < array[right]) {
return right;
} else {
return mid;
}
}
}
//Hoare版
private static int partitionHoare(int[] array, int left, int right) {
int tmp = array[left];
//记录一下该位置基准值
int leftTmp = left;
while (left < right) {
//右边找小的，左边找，互换
while (left<right && tmp <= array[right]) {
right--;
}
while (left<right && tmp >= array[left]) {
left ;
}
//1.left和right没相遇时相互交换
swap(array,left,right);
}
///2.left和right相遇时和基准值交换
swap(array,right,leftTmp);
return left;
}
//挖坑法
private static int partition(int[] array, int left, int right) {
int tmp = array[left];
int leftTmp = left;
while (left < right) {
while (left<right && tmp <= array[right]) {
right--;
}
array[left] = array[right];
while (left<right && tmp >= array[left]) {
left ;
}
array[right] = array[left];
}
array[left] = tmp;
return left;
}
//前后指针法：
private static int partition2(int[] array, int left, int right) {
int prev = left ;
int cur = left 1;
while (cur <= right) {
if(array[cur] < array[left] && array[ prev] != array[cur]) {
swap(array,cur,prev);
}
cur ;
}
swap(array,prev,left);
return prev;
}非递归写法：这里我们借助栈，让你两边越来越有序
代码语言：javascript复制//非递归实现快速排序：
public static void quickSortNor(int[] array) {
quickSort1(array,0,array.length-1);
}
public static void quickSort1(int[] array,int start,int end) {
//1.找相遇start和end点
int pivot = partition(array,start,end);
Deque<Integer> stack = new ArrayDeque<>();
//2.把pivot分开的两边元素放入，栈中
if (pivot > start 1) {
stack.push(start);
stack.push(pivot-1);
}
if (pivot < end-1) {
stack.push(pivot 1);
stack.push(end);
}
//3.把栈中元素弹出，直到栈为空
while (!stack.isEmpty()) {
end = stack.pop();
start = stack.pop();
//2.再找start和end相遇的点，把pivot分开的两边元素放入，再把栈中元素弹出，直到栈为空，数据有序
pivot = partition(array,start,end);
if (pivot > start 1) {
stack.push(start);
stack.push(pivot-1);
}
if (pivot < end-1) {
stack.push(pivot 1);
stack.push(end);
}
}
}4 快速排序总结：
1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
2. 时间复杂度：O(N*logN)
3.空间复杂度：最坏情况O(N)，最好情况：O(logN)
当然这个排序也有缺点不优化情况下：当数据本来就有序时，会递归很多层，可能会压爆栈。
4.归并排序：
1.基本思想：
归并排序是建立在归并操作上的一种有效的排序算法 , 该算法是采用分治法 的一个非常典型的应用。 将已有序的子序列合并，得到完全有序的序列； 就是先使每个子序列有序，再使子序列段间有序 。若 将两个有序表合并成一个有序表 ，称为二路归并。
图解：
代码：这里也有递归和非递归写法
代码语言：javascript复制/**归并排序：
* 时间复杂度：O(N*logN)
* 空间复杂度：O(N)
* 稳定性：稳定
*
* @param array
*/
public static void mergeSort(int[] array) {
int right = array.length-1;
mergeSortTmp(array,0,right);
}
private static void mergeSortTmp(int[] array, int left, int right) {
//递归返回条件
if (left >= right) {
return;
}
//分散数组
int mid = (left right) / 2;
mergeSortTmp(array,left,mid);
mergeSortTmp(array,mid 1,right);
//归并数组
merge(array,left,mid,right);
}
//归并数组
private static void merge(int[] array, int left,int mid, int right) {
//1.先合并两个有序数组
int[] tmp = new int[right-left 1];
int k = 0;
int s1 = left;
int e1 = mid;
int s2 = mid 1;
int e2 = right;
while (s1 <= e1 && s2 <= e2) {
if (array[s1] < array[s2]) {
tmp[k ] = array[s1 ];
}else {
tmp[k ] = array[s2 ];
}
}
while (s1 <= e1) {
tmp[k ] = array[s1 ];
}
while (s2 <= e2) {
tmp[k ] = array[s2 ];
}
//2.把分解合并后的数组，放回原数组
for (int i = 0; i < k; i ) {
array[i left] = tmp[i];
}
}
//非递归实现 归并排序：
public static void mergeSortNor(int[] array) {
//把数组看作gap组进行，分解然后合并
int gap = 1;
while (gap < array.length) {
for (int i = 0; i < array.length; i =i gap * 2) {
int left = i;
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,mid,right);
}
gap *= 2;
}
}归并排序总结
1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(N)
4. 稳定性：稳定
三.计数排序（了解）：
图解：
代码：
代码语言：javascript复制 /**
* 计数数组排序：
* 时间复杂度：O(范围 N) ，范围越大复杂度越大
*
* 空间复杂度：时间复杂度：O(范围)
* 稳定性：稳定（而这个代码的写法不稳定）
* @param array
*/
public static void countSort(int[] array) {
//1.遍历要排序数组，找出做大值最小值，确定计数数组长度
int maxVal = 0;
int mixVal = 0;
for (int i = 1; i < array.length; i ) {
if (array[i] < mixVal) {
mixVal = array[i];
}
if (array[i] > maxVal) {
maxVal = array[i];
}
}
int len = maxVal - mixVal 1;
int[] count = new int[len];
//2.遍历要排序数组，把明每个元素放入对应的计数数组中，进行计数
for (int i = 0; i < array.length; i ) {
int index = array[i];
//计数数组的下标要等于，array数组对应的元素
count[index-mixVal] ;
}
int index = 0;
//3.遍历计数数组，把计数过的元素返回array数组
for (int i = 0; i < count.length; i ) {
while (count[i] != 0) {
//此时计数数组对应的下标就是对应的元素
array[index] = i mixVal;
index ;
count[i]--;
}
}
}
