[前言]
此文章参考自《数据结构（java版）》第三版，叶核亚
一、排序的基本概念：
（1）性能评价：取决于时间复杂度和空间复杂度。排序中的时间复杂度由元素的比较次数和移动次数决定
（2）稳定性：指关键字重复情况下的排序性能。例如：1 2 9 2 ，排序后1 2 2 9；第一个2仍在第二个2之前这样的排序是稳定的。
（3）内排序和外排序：内排序指待排序的数据元素全部存储在内存；外排序是指待排序的数据元素非常多，不嫩全部存储在内存中，需要存储在外部的存储介质上的数据分批导入内存，分批存储，以下只有内排序。
二、排序的种类
1.插入排序：直接插入排序和折半插入排序、希尔排序
2.交换排序：冒泡排序、快速排序
3.选择排序：直接选择排序、堆排序
4.归并排序
5.单链表排序：单链表直接插入排序、单链表直接选择排序、单链表的归并排序
三、图解排序：
1.直接插入排序：
image
2.希尔排序：
image
3.冒泡排序：
image
4.快速排序
第一趟排序的过程：
image
排序的过程
image
5.选择排序
image
6.堆排序
最小堆和最大堆
image
创建最小堆：
image
排序的过程：
image
7.归并排序
一次归并：
image
归并排序过程：
image
四、排序源码：
（1）直接插入排序：（以下是一个完整的程序直接粘贴复制到eclipse就可以运行的）
package renee;
import java.util.Scanner;
public class sort{
//插入排序
public static void insertSort(int[] table){
for (int i=1;i<table.length;i++){
int temp = table[i],j;
for(j=i-1;j>=0&&temp<table[j];j--)
table[j+1] = table[j];
table[j+1] = temp;
}
}
public static void main(String[] args){
int number1;
Scanner num = new Scanner(System.in);
System.out.print("input how many number do you want to sort:");
number1 = num.nextInt();
int a[] = new int[number1];
System.out.print("Now put them in:");
for(int i=0;i<a.length;i++)
a[i] = num.nextInt();
insertSort(a); //执行排序
for(int i=0;i<a.length;i++){
System.out.print(a[i]+" ");
}
}
}
（2）冒泡排序（在执行排序那行添加 bubbleSort(a);即可运行，下同）
public static void bubbleSort(int[] table){
boolean exchange = true;
for(int i = 1;i<table.length&&exchange;i++){
exchange = false;
for(int j=0;j<table.length-i;j++)
if(table[j]>table[j+1]){
int temp = table[j];
table[j] = table[j+1];
table[j+1] = temp;
exchange = true;
}
}
}
（3）选择排序
public static void selectSort(int[] table){
for(int i=0;i<table.length-1;i++){
int min=i;
for(int j=i+1;j<table.length;j++)
if(table[j]<table[min])
min=j;
if(min!=i){
int temp = table[i];
table[i] = table[min];
table[min] = temp;
}
}
}
（4）堆排序
public static void heapSort(int[] table){
int n = table.length;
for(int j=n/2;j>=0;j--)
sift(table,j,n-1);
for(int j=n-1;j>0;j--){
int temp = table[0];
table[0] = table[j];
table[j] = temp;
sift(table,0,j-1);
}
}
private static void sift(int[] table,int begin,int end){
int i=begin,j=2*i+1;
int temp = table[i];
while(j<=end){
if(j<end&&table[j]>table[j+1])
j++;
if(temp>table[i]){
table[i] = table[i];
i=j;
j=2*i+1;
}
else break;
}
table[i] = temp;
}
（5）归并排序
public static void merge(int[] X,int[] Y,int m,int r,int n){ //一次归并
int i=m,j=r,k=m;
while(i<r&&j<r+n&&j<X.length) //将X中两个相邻子序列归并到Y中
if(X[i]<X[j]) //将较小值复制到Y中
Y[k++]=X[i++];
else
Y[k++]=X[j++];
while(i<r){
Y[k++]=X[i++]; //将前一个子序列剩余元素复制到Y中
while(j<r+n&&j<X.length)
Y[k++]=X[j++]; //将后一个子序列剩余元素复制到Y中
}
}
//归并排序-一趟归并
private static void mergepass(int[] X,int[] Y,int n){ //一趟归并
int i=0;
while(i<X.length-2*n+1){
merge(X,Y,i,i+n,n);
i += 2*n;
}
if(i+n<X.length)
merge(X,Y,i,i+n,n); //再一次归并
else
for (int j=i;j<X.length;j++)
Y[j]=X[j]; //将X剩余元素复制到Y中
}
//归并排序
public static void mergeSort(int[] X){ //归并排序
int[] Y = new int[X.length]; //将Y数组长度同X数组
int n = 1; //已排序的子序列长度，初值为1
while(n<X.length){
mergepass(X,Y,n); //一趟归并，将X数组中各子序列归并到Y中
n*=2; //子序列长度加倍
if(n<X.length){
mergepass(Y,X,n); //将数组中各子序列再归并到X中
n*=2;
}
}
}
