目录
一、前言
关于各种排序问题，是笔试面试中的经典问题，很多同学表示看的时候都懂了，用的时候全混了（没错就是我==）。所以为了方便复习（预习），下面整理了各种算法思想以及复杂度，当然还有代码实现。
二、七种经典排序
1.直接选择排序
简单来说，选择排序就是每次找未排序数组中的最小（或者最大）的记录并固定其位置
* 思想： ①对于给定的一组记录，经过第一轮比较后得到最小的记录，然后将该记录与第一个记录的位置进行交换；
②接着对不包括第一个记录之外的其他记录进行第二轮比较，得到最小的记录并与第二个记录进行位置交换；
③重复该过程 直到全部排序
*时间复杂度：最好 最坏 平均时间均为O（n^2）
*辅助空间：O（1）
*稳定性：不稳定
Java代码实现直接选择排序：
public class SelectSort {
public static void selectSort(int[] a) {
int temp = 0; //用来放每趟中的最小值
int index = 0; //用来放上面最小值temp对应的数组下标
int len = a.length; //数组长度
for(int i=0;i<len;i++) {//某一趟
temp = a[i];
index = i;
for(int j=i+1;j<len;j++) { //在该趟找出未排序部分的最小值放temp中，从前往后依次比较
if(a[j] < temp) {
temp = a[j];
index = j;
}
}
if(index != i) { //找到最小值位置且不是a[i]，就进行交换
a[index] = a[i];
a[i] = temp; //交换第i个位置数据
}
}
}
public static void main(String[] args) {
int[] array = {5,4,3,7,6,8,10,1};
System.out.print("原数组：");
for(int ai : array) {
System.out.print(ai+" ");
}
System.out.println();
selectSort(array);
System.out.print("选择排序后：");
for(int ai : array) {
System.out.print(ai+" ");
}
}
}2.直接插入排序
* 算法思想： 初始时假设第一个记录自成一个有序序列，其余记录均为无序序列。
* 接着从第二个记录开始，按照记录的大小依次将当前处理的记录插入到其之前的有序序列中，
* 直到最后一个记录插入到有序序列中为止
* 时间复杂度：最好时间：O（n）；最坏 平均：O（n^2）
* 辅助空间：O（1）
* 稳定性：稳定的！！！
Java代码实现插入排序：
public class InsertSort {
public static void insertSort(int[] a) {
int len = a.length; //数组的长度
if(a != null) {
for(int i=1;i<len;i++) { //注意啦 i从1开始循环
int temp = a[i]; //存放即将要插入的数据
int j = i;
if(a[j-1] > temp) { //将temp从后往前依次比较
while(j>=1 && a[j-1]>temp) {
a[j] = a[j-1];
j--;
}
/*for(;j>=1 && a[j-1]>temp;j--) { //这句与上面的while循环等价
a[j] = a[j-1];
}*/
}
a[j] = temp; //确定要插入的位置了
}
}
}
public static void main( String[] args ) {
int[] array = {5,4,3,7,6,8,10,1};
System.out.print("原数组：");
for(int ai : array) {
System.out.print(ai+" ");
}
System.out.println();
insertSort(array);
System.out.print("插入排序后：");
for(int ai : array) {
System.out.print(ai+" ");
}
}
}3.冒泡排序
* 算法思想：① 对于给定的n个记录，从第一个记录开始依次对相邻相邻相邻的两个记录进行比较，当前面记录大于后面的记录时，交换位置，进行一轮比较和换位后，最大的纪录将位于第n位；
* ②然后对前（n-1）个记录进行第二轮比较；
* ③重复该过程直到进行比较的记录只剩下一个
* 时间复杂度：最好时间：O（n） ； 最坏和平均：O（n^2）
* 辅助空间：O（1）
* 稳定性：稳定的！！！
Java代码实现冒泡排序：
public class BubbleSort {
public static void bubbleSort(int[] a) {
int len = a.length; //数组长度
int temp; //辅助空间
for(int i=len-1 ; i>=0 ; i--) {
for(int j=0 ; j<i ; j++) { //从前往后依次比较
if(a[j] > a[j+1]) { //前一个比后一个大，就进行交换
temp = a[j+1];
a[j+1] = a[j];
a[j] = temp;
}
}
}
}
public static void main( String[] args ) {
int[] array = {5,4,3,7,6,8,10,1};
System.out.print("原数组：");
for(int ai : array) {
System.out.print(ai+" ");
}
System.out.println();
bubbleSort(array);
System.out.print("冒泡排序后：");
for(int ai : array) {
System.out.print(ai+" ");
}
}
}4.归并排序
*思想： 利用递归与分治技术将数据序列划分为越来越小的半子表，再对半子表排序，最后用递归将排好序的半子表合并为越来越大的有序序列。
* ① “归”--表示递归，即递归将数组折半地分为单个数组
* ② “并”--表示合并，即将分开的数据按照从小到大或从大到小的顺序再放到一个数组中
* ③对于给定一组记录，首先将每两个相邻的长度为1的子序列进行归并，得到【n/2】(向上取整)个长度为2或者1的有序子序列，再将其两两归并；反复执行此过程直到得到一个有序序列
* 时间复杂度：最好、 最坏、 平均时间：O（n*log n）
*辅助空间：O（n）
*稳定性：稳定的！！！
Java代码实现归并排序：
public class MergeSort {
/*
* 1.将两个有序数组进行合并，a[first,mid] 和 a[mid+1,last]
*/
public static void mergeArray(int[] a, int first, int mid, int last, int[] temp){
int i = first, j = mid+1; //设置两个数组的起始下标
int m = mid, n = last; //设置两个数组结束下标,俩数组变为a[i,m],a[j,n]
int k = 0; //辅助数组temp[]的下标
while(i<=m && j<=n) { //两个数组均未到达末尾时,每次将较小的值赋给temp[k]
if(a[i] <= a[j]) {
temp[k++] = a[i++];
}else {
temp[k++] = a[j++];
}
}
while(i <= m) { //第一个数组还有数据，第二个数组完事了，直接将第一个剩下的复制到temp中
temp[k++] = a[i++];
}
while(j <= n) { //第二个数组还有数据，第1个数组完事了，直接将第2个剩下的复制到temp中
temp[k++] = a[j++];
}
for(i=0 ; i<k ; i++) {
a[first+i] = temp[i]; //将排好序的部分复制回去原数组，即更新原数组a[first,last]
}
}
/*
* 2.二路归并排序，递归实现
*/
public static void mergeSort(int[] a, int first, int last, int[] temp) {
if(first < last) {
int mid = (first + last)/2;
mergeSort(a, first, mid, temp); //将原数组左半部分排序，递归
mergeSort(a, mid+1, last, temp); //将原数组右半部分排序，递归
mergeArray(a, first, mid, last, temp); //合并两个有序的数组
}
}
public static void main( String[] args ) {
int[] array = {99,5,4,3,7,6,8,10,-1,1};
int[] temp = {0,0,0,0,0,0,0,0,0,0};
System.out.print("原数组：");
for(int ai : array) {
System.out.print(ai+" ");
}
System.out.println();
mergeSort(array,0,array.length-1,temp);
System.out.print("归并排序后：");
for(int ai : array) {
System.out.print(ai+" ");
}
}
}5.快速排序
*思想： “分而治之”
* ① 对于一组给定的记录，通过一趟排序后，将原序列分为两部分，其中前一部分的所有记录均比后一个序列的记录小；
* ② 然后再依次对前后两部分的记录进行快速排序
* 时间复杂度：最坏时间：O（n^2）； 最好和平均：O（n*log n）
* 辅助空间：O（log n）
*稳定性：不稳定的
* 注意啦！快排是所有平均时间复杂度为O（n*log n）算法中，平均性能最好的！！
Java代码实现快排：
public class QuickSort {
/*
* 快速排序的递归实现。输入：数组，最小下标，最大下标
*/
public static void quickSort(int[] a, int low, int high) {
if(low >= high) {
return;
}
int i = low;
int j = high;
int index = a[i]; //用于比较的关键字（基准值）
while(i < j) { //这是一趟排序
while(i<j && a[j]>index) { //从后往前找第一个比index小的数a[j]
j--;
}
if(i < j) {
a[i] = a[j]; //找到之后将该值赋给a[i]，并将i++
i++;
}
while(i<j && a[i]<index) { //从前往后找第一个比index大的数a[i]
i++;
}
if(i < j) {
a[j] = a[i]; //找到之后将该值赋给a[j]，并将j--
j--;
}
}
a[i] = index; //一趟排序结束后，固定本次基准值的位置
quickSort(a,low,i-1); //前半部分继续快排
quickSort(a,i+1,high); //后半部分继续快排
}
public static void main( String[] args ) {
int[] array = {99,-1,5,4,3,7,6,8,10,1};
System.out.print("原数组：");
for(int ai : array) {
System.out.print(ai+" ");
}
System.out.println();
quickSort(array,0,array.length-1);
System.out.print("快速排序后：");
for(int ai : array) {
System.out.print(ai+" ");
}
}
}6.希尔排序
* 希尔排序也叫“缩小增量排序”
* 思想：①.首先选择一个步长序列，t1=n/2, t2=t1/2, ... ,tk=1；如n=10,则步长序列{5,2,1}
②.然后按步长序列个数k，对待排序序列进行k趟排序；
③.每趟排序，根据对应步长ti,将待排序列分成ti个子序列，分别对各个子序列进行直接插入排序。
* 时间复杂度：最坏 平均：O（n*log n）//也有地方写O（n^1.25）
* 辅助空间：O（1）
* 稳定性：不稳定
Java代码实现希尔排序：
public class ShellSort {
public static void shellSort(int[] a) {
int len = a.length; //数组长度
int temp; //辅助空间
int i,j,h;
for(h=len/2; h>0; h=h/2 ) { //1.h表示步长，从len/2一直变化到1
for(i=h; i<len; i++){ //2.然后按步长序列数组个数k，对待排序序列进行k趟排序；
temp = a[i];
for(j=i-h; j>=0; j=j-h) { //3.每趟排序，根据对应步长ti,将待排序列分成ti个子序列，分别对各个子序列进行直接插入排序。
if(temp < a[j]) {
a[j+h] = a[j];
} else {
break;
}
}
a[j+h] = temp;
}
}
}
public static void main( String[] args ) {
int[] array = {99,-1,5,4,3,7,6,8,10,1};
System.out.print("原数组：");
for(int ai : array) {
System.out.print(ai+" ");
}
System.out.println();
shellSort(array);
System.out.print("希尔排序后：");
for(int ai : array) {
System.out.print(ai+" ");
}
}
}7.堆排序
* 思想：① 对于给定的n个记录，初始时把这些记录看作是一棵顺序存储的二叉树，然后将其调整为一个小顶堆（或大顶堆）
② 然后将堆的最后一个元素与堆顶元素（即根节点）进行交换后，堆的最后一个元素即为最小（或最大）记录；
③ 接着将前（n-1）个元素进行重新调整为一个小顶堆（或大顶堆），再将堆顶元素与与当前堆的最后一个元素进行交换后，得到次小（或次大）记录；
④ 重复上述过程直到堆中只剩一个元素为止
* 即主要包括：1.构建堆；2.交换堆顶元素与最后一个元素位置
* 时间复杂度：最好、 最坏、 平均：O（n*log n）
* 辅助空间：O（1）
* 稳定性：不稳定
Java代码实现堆排序：
public class MinHeapSort { //小根堆最后是从大到小排序
/**
* //建堆：比较当前父节点是否大于子节点，如果大于就交换，直到一趟建堆完成～
* @param a 将数组a看作是完全二叉树
* @param pos 当前父节点位置
* @param len 节点总数
*/
public static void adjustMinHeap(int[] a, int pos, int len) {
int temp; //辅助空间
int child;
for(temp=a[pos]; 2*pos+1<=len; pos=child) {
child = 2*pos+1; //左子树位置
if(child<len && a[child]>a[child+1]) { //!!要想使得排序从大到小，需将a[child]<a[child+1]
child++; //左孩子比右孩子大，将child更新为右子树位置
}
if(a[child] < temp) { //!!要想使得排序从大到小，需将a[child] > temp.只需要改这俩地方即可
a[pos] = a[child]; //当孩子节点比父节点小时，将孩子节点赋给父节点，即更新当前节点
} else {
break;
}
}
a[pos] = temp; //完成一次建堆，temp为最小值，放在根节点处
}
public static void minHeapSort(int[] a) {
int len = a.length;
for(int i=len/2-1; i>=0; i--) {
adjustMinHeap(a,i,len-1); //1.初始建堆
}
for(int i=len-1; i>=0; i--) {
int temp = a[0]; //2.交换堆顶元素与最后一个元素位置
a[0] = a[i];
a[i] = temp;
adjustMinHeap(a,0,i-1); //继续调整堆，循环上面过程
}
}
public static void main( String[] args ) {
int[] array = {99,-1,5,4,3,7,6,8,10,1};
System.out.print("原数组：");
for(int ai : array) {
System.out.print(ai+" ");
}
System.out.println();
minHeapSort(array);
System.out.print("小根堆排序后：");
for(int ai : array) {
System.out.print(ai+" ");
}
}
}三、总结
这七种经典排序均为内部排序，即只使用内存。可以分为以下几大类：
1. 插入排序包括：直接插入排序、希尔排序
2. 选择排序包括：直接选择排序、堆排序
3. 交换排序包括：冒泡排序、快速排序
4. 归并排序
