排序算法是面试笔试的一个重点，今天，就让我们把常见的排序算法总结一遍。
选择排序
思想：遍历一组记录，每次遍历选取一个最大的数（最小的数），来依次替代需要替代的位置（从头开始选择）。
源代码：
/**
* 选择排序
* @param a
* 时间复杂度 n的平方 最好，最差，平均都是
*/
public static void selectSort(int[] a){
int min;
int minNum = 0;
for(int i = 0;i < a.length;i++){
min = a[i];
for(int j = i + 1;j < a.length;j++){
if(min > a[j]){
min = a[j];
minNum = j;
}
}
a[minNum] = a[i];
a[i] = min;
}
for(int i = 0;i < a.length;i++){
System.out.print(a[i] + " ");
}
System.out.println();
}
插入排序
思想：假设一组数中，第一个数是有序的，其他数是无序的，将后面的数依次插入到前面有序的数中，直到最后。
源代码：
/**
* 插入排序
* 事件复杂度为 n的平方，，，最好为n
*/
public static void insertSort(int[] a){
for(int i = 1;i < a.length;i++){
int j = i;
int num = a[i];
if(num < a[i-1]){
while(a[j-1]>num&&j>=1){
a[j] = a[j - 1];
j--;
}
}
a[j] = num;
}
for(int i = 0;i < a.length;i++){
System.out.print(a[i] + " ");
}
}
冒泡排序
思想：像气泡一样往上升，就是从第一个记录开始，对相邻的记录进行比较，当前面的额数大于后面的数时交换位置，继续比较下一个相邻的，一趟后，最大的数位于最后面，同理第二轮最大的数位于倒数第二个。
源代码：
/**
* 冒泡排序
* 时间复杂度
*/
public static void BubbleSort(int array[]){
int j = 0;
for(int i = 0;i < array.length - j;j++){
if (array.length - j == 0)
break;
for(int k = 0;k < array.length - j - 1;k++){
if(array[k] > array[k+1]){
int num = array[k];
array[k] = array[k+1];
array[k+1] = num;
}
}
}
for(int i = 0;i < array.length;i++){
System.out.print(array[i] + " ");
}
System.out.println();
}
归并排序
思想：利用递归与分治技术将数据划分为越来越小的半子表。先将数组分成长度为1的子序列，然后进行两两归并，得到长度为2或1的子序列，继续两两归并，直到完整。
源代码：
/**
* 归并排序
*/
public static void Merge(int array[],int left,int mid,int right){
int[] L = new int[mid-left+1];
int[] R = new int[right-mid];
for(int i = 0,j = left;j <= mid;i++,j++){
L[i] = array[j];
}
for(int i = 0,j = mid + 1;j <= right;i++,j++)
R[i] = array[j];
int i=0,j=0,k=left;
for(;i < L.length && j < R.length;k++){
if(L[i] > R[j]){
array[k] = R[j];
j++;
}else{
array[k] = L[i];
i++;
}
}
if(i < L.length){
for(;i < L.length;i++){
array[k] = L[i];
k++;
}
}
if(j < R.length){
for(;j < R.length;j++){
array[k] = R[j];
k++;
}
}
}
public static void MergeSort(int array[],int left,int right){
if(left < right){
int mid = (right + left)/2;
MergeSort(array, left, mid);
MergeSort(array, mid+1, right);
Merge(array, left, mid, right);
}
}
快速排序
思想：顾名思义，快速排序是一种很有效率的算法。采用的思想是“分而治之”，方法是递归。步骤是将一组数据分成两部分，前一部分均比后一部分小，然后继续对前后部分进行快速排序，递归到所有数据有序。 大概步骤：分解—>递归求解—>合并
/**
* 快速排序
*/
public static void quickSort(int array[],int left,int right){
int i,j;
if(left >= right)
return;
i = left;
j = right;
int num = array[left];
while(i < j){
while(array[j] >= num && i < j){
j--;
}
if(array[j] < num){
array[i] = array[j];
i++;
}
while(array[i] < num && i < j){
i++;
}
if(array[i] >= num){
array[j] = array[i];
j--;
}
}
array[i] = num;
quickSort(array,left,i-1);
quickSort(array,i+1,right);
}
快速排序相关知识点：
- 最坏的时间复杂度。当选取的基准关键字，也就是代码中的num，是最大的数或者是最小的数时，此时需要划分（n-1）次区间，此时的时间复杂度为$[O\left( ^2}} \right)] $
- 最好的时间复杂度。就是选取的基准关键字左右两边长度相等或者相差1，就是说基准关键字就是中间值，这样时间复杂度为$[O\left( {n\log n} \right)]$
- 平均时间复杂度。快速排序的平均复杂度是$[O\left( {n\log n} \right)]$，虽然最差的时间复杂度为$[O\left( ^2}} \right)]$，快速排序的平均性能最好。
- 空间复杂度。快速排序需要一个栈辅助进行递归，平均空间复杂度为$[O\left( {\log n} \right)]$
- 基准关键字的选取。基准关键字的选取是快速排序性能的体现，所以有不同的基准关键字的选取方式。第一种是三者取一，就是选取最左边、中间、最右边的数进行比较，选取中间值最为基准关键字；第二种是取随机数，就是在取一个随机数作为基准关键字。
希尔排序
思想：先将待排序的数组分成多个子序列，然后对子序列直接进行插入排序，然后当整个待排序序列基本有序后，最后对所有元素进行直接排序。
源代码：
/**
* 希尔排序
*/
public static void shellSort(int array[]){
int length = array.length;
int h,j;
for(h = length/2;h > 0;h = h/2){
for(int i = h;i < length;i++){
int temp = array[i];
for(j = i - h;j >= 0;j = j - h){
if(temp < array[j]){
array[j + h] = array[j];
}else{
break;
}
}
array[j + h] = temp;
}
}
}
堆排序
堆是一种特殊的树形结构数据，每个节点都有一个值，通常提到的堆都是指一颗完全二叉树，根节点的值大于或者小于两个节点的值。 思想：对于给定的n个记录，将这些记录看成一颗顺序存储的二叉树，然后将其调整为一个大顶堆，然后将堆的最后一个元素和堆顶的元素交换，继续讲剩余的n-1个记录重新构造堆，直到堆中只剩一个元素。
/**
* 堆排序
*/
public static void adjustMinHeap(int[] array,int pos,int len){
int temp;
int child;
for(temp = array[pos];2 * pos + 1 <= len;pos = child){
child = 2 * pos + 1;
if(child < len && array[child] > array[child + 1])
child++;
if(array[child] < temp)
array[pos] = array[child];
else
break;
}
array[pos] = temp;
}
public static void myMinHeapSort(int[] array){
int i;
int len = array.length;
for(i = len/2 - 1;i >= 0;i--)
adjustMinHeap(array,i,len-1);
for(i = len - 1;i >= 0;i--){
int temp = array[0];
array[0] = array[i];
array[i] = temp;
adjustMinHeap(array,0,i-1);
}
}
总结：
稳定的排序算法：直接插入排序，冒泡排序，归并排序 不稳定的排序算法：希尔排序、快速排序、简单选择排序、堆排序
时间复杂度为$[O\left( ^2}} \right)]$的算法：直接插入排序、冒泡排序、快速排序、简单选择 时间复杂度为$[O\left( {n\log n} \right)]$的算法为：归并排序、堆排序
空间复杂度为$[O\left( 1 \right)]$的算法为：简单选择、直接插入、冒泡排序、希尔排序、堆排序 空间复杂度为$[O\left( {\rm{n}} \right)]$的算法为：归并排序 空间复杂度为$[O\left( } \right)]$的算法为：快速排序
初始序列整体或部分有序时，插入和冒泡排序有较高的效率，快速排序效率会下降。 数列小，且要求不稳定，用选择排序效率高，要求稳定用冒泡。
