各种排序算法实现原理和代码及适用范围总结
排序算法可以分为内部排序和外部排序，内部排序又可以分为插入类、交换类、选择类、归并类排序，归并排序通常也应用于外部排序，但采用的是多路归并排序。
内部排序有：
插入类排序：直接插入、折半插入、希尔排序；
交换类排序：冒泡排序、快速排序；
选择类排序：简单（直接）选择排序、堆排序；
归并类排序：归并排序；
外部排序：需要在内外存之间多次交换数据才能进行；
1、直接插入排序
基本思路：L(i)为待排序表中一个元素，前一子序列 L[1…i-1]为有序子序列，后一子序列 L[i+1…n]为无序子序列，为了实现将元素 L(i)插入到已有序的子序列 L[1…i-1]中，需进行以下操作：
1）查找出 L(i)在 L[1…i-1]中的插入位置 k；
2）将 L[k…i-1]中所有元素全部后移一个位置；
3）将 L(i)复制到 L(k)。
过程：就是将后面无序子序列中的每一个元素依次往前面有序子序列中插入到相应的位置，初始时将待排序列的第一个元素作为有序子序列的一个元素。
Java 代码实现：
import java.util.Scanner;
//用 Java 实现直接插入排序
public class DirectInsertSort {
public static void InsertSort(int A[],int n){
int k,j;
for(int i=1;i<n;i++){
if(A[i]<A[i-1]){
k = A[i];
for(j=i-1;j>=0 && k<A[j];j–){
A[j+1]=A[j];
}
A[j+1]=k;
}
}
}
public static void main(String [] args){
int A[] = new int[10];
System.out.println(“请输入数值插入到已声明的数组中：”);
Scanner reader = new Scanner(System.in);
for(int i = 0;i<A.length;i++)
{
//System.out.println(“请输入第”+(i+1)+”个数字：”);
int In = reader.nextInt();
A[i] = In;
}
InsertSort(A,A.length);
System.out.println(“排序后的数组元素序列为：”);
for(int i = 0;i<A.length;i++){
System.out.print(A[i]+” “);
}
}
}
时间复杂度：最好情况下 O(n),表中元素基本有序，每插入一个元素，都只需比较一次而不用移动元素，最坏情况和平均情况下都是 O(n^2),最坏情况是表中元素基本逆序，平均情况下指待排序表中元素是随机的。
空间的复杂度：O(1)
直接插入排序是一个稳定的排序方法。
2、折半插入排序
基本思路：上面的直接插入排序算法在每趟插入的过程中都进行了两项工作：1）从前面的字表中 查找出待插入元素应该被插入的位置；2)给插入位置腾出空间，将待插入元素复制到表中的插入位置；边比较边移动元素。而折半插入排序是将比较和移动操作分离开来，先折半查找出元素的待插入位置，在统一移动待插入位置之后的所有元素，当采用顺序存贮的线性表且数据量较小时可以采用折半插入排序算法，另一方面查找有序子表时采用折半查找来实现。
Java 代码实现：
import java.util.Scanner;
public class ZheBanInsertSort {
public static void ZheBan_InsertSort(int A[],int n){
int i,j,k,low,high,mid;
for(i=1;i<n;i++){
k = A[i];
low = 0;high = i-1;
while(low<=high){//折半查找，确定查找位置
mid = (low+high)/2;
if(k<=A[mid])
high = mid-1;
else
low = mid+1;
}
for(j=i-1;j>=high+1;j–){
A[j+1] = A[j];//统一后移元素，空出插入位置
}
A[high+1] = k;
}
}
public static void main(String [] args){
int A[] = new int[10];
System.out.println(“请输入数值插入到已声明的数组中：”);
Scanner reader = new Scanner(System.in);
for(int i = 0;i<A.length;i++)
{
//System.out.println(“请输入第”+(i+1)+”个数字：”);
int In = reader.nextInt();
A[i] = In;
}
ZheBan_InsertSort(A,A.length);
System.out.println(“排序后的数组元素序列为：”);
for(int i = 0;i<A.length;i++){
System.out.print(A[i]+” “);
}
}
}
时间复杂度：折半插入排序仅仅是减少了比较元素的次数，约为 O(nlogn),与待排序表的初始状态无关，仅取决于表中的元素个数 n，而元素的移动次数没有改变，仍为 O(n^2)，因此时间复杂度为 O(nlogn)+O(n^2)=O(n^2)。
空间复杂度：O(1)
折半插入排序是一个稳定的排序方法。
3、希尔排序
直接插入排序算法适用于基本有序的排序表和数据量不大的排序表，基于这两点提出希尔排序，或称为缩小增量排序。
基本思路：先将待排序表分割成若干个形如 L[i,i+d,i+2d,…i+kd]的“特殊”子表，分别进行直接插入排序，当整个表中元素局部基本有序时再对全体记录进行一次直接插入排序（最后一趟）。先取一个小于 n 的步长 d1,把表中全部记录分成 d1 个组，所有距离为 d1 的倍数的记录放在同一个组中，在各组中进行直接插入排序；然后取第二个步长 d2<d1，重复上述过程，直到所取到的 dt=1，即所有记录已放在同一组中，在进行直接插入排序，此时已经具有较好的局部有序性，因此可以很快得到排序结果。
Java 代码如下：
import java.util.Scanner;
public class SellSort {
public static void ShellSort1(int A[],int n){
int i,j,k,dk=n/2;
while(dk>0){
for(i = dk+1;i<n;i++){
k = A[i];
j = i-dk;
while(j>=0&&k<A[j]){
A[j+dk] = A[j];
j = j-dk;
}
A[j+dk] = k;
}
dk = dk/2;
}
}
public static void ShellSort2(int A[],int n){
int i,j,k,dk;
for(dk=n/2;dk>=1;dk=dk/2){
for(i=dk+1;i<n;i++){
if(A[i]<A[i-dk]){
k = A[i];
for(j=i-dk;j>=0&&k<A[j];j=j-dk)
A[j+dk] = A[j];
A[j+dk] = k;
}
}
}
}
public static void main(String [] args){
int A[] = new int[10];
System.out.println(“请输入数值插入到已声明的数组中：”);
Scanner reader = new Scanner(System.in);
for(int i = 0;i<A.length;i++)
{
//System.out.println(“请输入第”+(i+1)+”个数字：”);
int In = reader.nextInt();
A[i] = In;
}
ShellSort1(A,A.length);
//ShellSort2(A,A.length);
System.out.println(“排序后的数组元素序列为：”);
for(int i = 0;i<A.length;i++){
System.out.print(A[i]+” “);
}
}
}
时间复杂度：最好情况下为 O(n^1.3)，最坏情况下为 O(n^2)，平均情况下为 O(nlogn)~O(n^2)
空间复杂度：O(1)
希尔排序是一个不稳定的排序算法，仅适用于线性表为顺序存储的情况
4、冒泡排序
基本思路：假设待排序表长为 n，从前往后或从后往前两两比较相邻元素值，若为逆序，则交换两者的顺序，直到序列比较完，称为一趟冒泡排序，共进行 n-1 趟冒泡过程。
这里例举三个冒泡排序过程，他们移动和交换元素的次数都不相同：
//第一种冒泡排序算法,性能最差的一种
public static void BubbleSort1(int a[],int n){
int i,j;
for(i=0;i<n;i++){//表示 n 次排序过程
for(j=1;j<n;j++){//一趟冒泡过程
if(a[j-1]>a[j]){//前面的数据大于后面的数据就交换
int temp;
temp = a[j-1];
a[j-1] = a[j];
a[j] = temp;
}
}
}
}
//第二种冒泡排序算法，减少了比较数据的次数
public static void BubbleSort2(int a[],int n){
int i,j;
for(i=0;i<n;i++){//表示 n 次排序过程
for(j=1;j<n-i;j++){//一趟冒泡过程
if(a[j-1]>a[j]){//前面的数据大于后面的数据就交换
int temp;
temp = a[j-1];
a[j-1] = a[j];
a[j] = temp;
}
}
}
}
//第三种冒泡排序算法
public static void BubbleSort3(int a[],int n){
Boolean exchange = true;
int k = n-1;
while(exchange){
exchange = false;
for(int i=0;i<k;i++){
if(a[i]>a[i+1]){
int temp;
temp = a[i];
a[i] = a[i+1];
a[i+1] = temp;
exchange = true;//交换后就置为 true
}
}
k = k-1;//最大值交换到最终位置，相应减 1，减少了比较和交换次数
}
}
数据验证代码：
public static void main(String args[]){
Scanner in = new Scanner(System.in);
System.out.println(“请从控制台输入数据：”);
//int a[]={10,56,32,98,75,12,3,59,87,16},i=0;
String str[] = in.nextLine().split(” “);//字符串以空格分隔，得到的是字符串
int num[] = new int[str.length];//创建并初始化数组，用于存储整形数据的数组，将字符串转为整型数据后存入 num 数组中
for(int i=0;i<str.length;i++){
num[i] = Integer.parseInt(String.valueOf(str[i]));
}
//while(in.hasNextInt()){
// a[i++]=in.nextInt();
//BubbleSort1(a,a.length);
//}
System.out.println(“排序前转为数组中的整型数据为：”);
for(int i=0;i<num.length;i++){
System.out.print(num[i]+” “);
}
System.out.println(“\n 使用三种冒泡排序算法排序后的结果为”);
int[] num_Bubble1 = num;
int[] num_Bubble2 = num;
BubbleSort1(num_Bubble1,num_Bubble1.length);//使用冒泡排序算法 1 对数据进行排序
System.out.println(“排序后的数组中的数据为：”);
for(int i=0;i<num_Bubble1.length;i++){
System.out.print(num_Bubble1[i]+” “);
}
BubbleSort2(num_Bubble2,num_Bubble2.length);//使用冒泡排序算法 2 对数据进行排序
System.out.println(“\n 排序后的数组中的数据为：”);
for(int i=0;i<num_Bubble2.length;i++){
System.out.print(num_Bubble2[i]+” “);
}
BubbleSort3(num_Bubble2,num_Bubble2.length);//使用冒泡排序算法 2 对数据进行排序
System.out.println(“\n 排序后的数组中的数据为：”);
for(int i=0;i<num.length;i++){
System.out.print(num[i]+” “);
}
}
时间复杂度：最好情况下（初始序列基本有序时）O(n)，平均情况下和最坏情况下都为 O(n^2)
空间复杂度：O(1)
冒泡排序是一个稳定的排序算法
5、快速排序
基本思路：快速排序是对冒泡排序的一种改进，基本思想是基于分治法的：在待排序表 L[1…n]中任取一个元素（一般是待排序表的第一个元素）作为基准，通过一趟排序将待排序表划分为独立的两部分 L[1…k-1]和 L[k+1…n]，使得 L[1…k-1]中的所有元素小于基准元素，L[k+1…n]中的所有元素大于或等于基准元素，基准元素放在了最终位置 L[k]上，这个过程称为一趟快速排序，后分别递归地对两个子表重复上述过程，直至每部分内只有一个元素或空为止，此时所有元素放在了其最终位置上。
Java 代码如下：
import java.util.Scanner;
public class QuickSort {
//基准划分操作过程
public static int Partition(int a[],int low,int high){
int pivot = a[low];//将当前表中第一个元素设为基准值，对表进行划分
while(low<high){
while(low<high && a[high]>=pivot)
high–;
if(low<high){
a[low] = a[high];
low++;
}
while(low<high && a[low]<pivot)
low++;
if(low<high){
a[high] = a[low];
high–;
}
}
a[low] = pivot;
return low;
}
//快速排序算法的递归过程
public static void QuickSort_recurrence(int a[],int low,int high){
if(low<high){//递归跳出条件
//Partition（）属于划分操作，将表 a[]划分为满足小于基准值的所有数据在左边大于基准值的所有数据在右边的两个子表
int pivotPosition = Partition(a,low,high);//基于基准值划分两部分
QuickSort_recurrence(a,low,pivotPosition-1);//依次对两个子表递归排序
QuickSort_recurrence(a,pivotPosition+1,high);
}
}
public static void main(String args[]){
System.out.println(“请输入待排序的数据到数组中：”);
Scanner sc = new Scanner(System.in);
String str[] = sc.nextLine().split(” “);//以空格相隔输入各个数据
int num[] = new int[str.length];//数组创建及初始化
for(int i=0;i<str.length;i++){
num[i] = Integer.parseInt(String.valueOf(str[i]));
}
QuickSort_recurrence(num,0,num.length-1);//调用快速排序算法进行排序
System.out.println(“排序后的结果为：”);
for(int i=0;i<num.length;i++){
System.out.print(num[i]+” “);
}
}
}
时间复杂度：最好情况下和平均情况下（数据元素随机分布）为 O(nlogn),最坏情况下（待排序表基本有序或基本逆序时）为 O(n^2)
空间复杂度：平均情况下为 O(logn)，最坏情况下为 O(n)
快速排序是所有内部排序算法中平均性能最优的排序算法，适用于元素随机分布的情况，是一个不稳定的排序算法。
6、简单（直接）选择排序
基本思路：第 i 趟在后面 n-i+1（i=1,2,3,…n-1）个待排序元素中选取关键字最小的元素，作为前面有序子序列的第 i 个元素，直到第 n-1 趟做完，待排序元素只剩下一个，就不用再选了，假设待排序表为 L[1…n]，第 i 趟排序即从 L[i…n]中选择关键字最小的元素与 L(i)交换，每一趟排序可以确定一个元素的最终位置，进行 n-1 趟就使排序表有序。
Java 代码如下：
import java.util.Scanner;
//简单（直接）选择排序
public class Direct_EasySelectSort {
public static void Direct_Easy_SelectSort(int a[],int n){
//对表 a 做简单选择排序，从 0 存储位置开始排序
for(int i=0;i<n-1;i++){//进行 n-1 趟
int min = i;
for(int j=i+1;j<n;j++){//在 a[i+1…n]数组中选择关键字最小的元素
if(a[j]<a[min])
min = j;//找出关键字最小的元素，记录它的数组下标
}
if(min!=i){//选择最小元素值与 a[i]元素交换位置
int temp = a[i];
a[i] = a[min];
a[min] = temp;
}
}
}
public static void main(String args[]){
System.out.println(“请输入待排序的数据到数组中：”);
Scanner sc = new Scanner(System.in);
String str[] = sc.nextLine().split(” “);
int num[] = new int[str.length];
for(int i=0;i<num.length;i++){
num[i] = Integer.parseInt(String.valueOf(str[i]));
}
Direct_Easy_SelectSort(num,num.length);//调用简单选择排序算法对数组中的数据进行排序
System.out.println(“排序后的数组元素为：”);
for(int i=0;i<num.length;i++){
System.out.print(num[i]+” “);
}
}
}
时间复杂度：由于元素间比较的次数与序列的初始状态无关，始终有 n(n-1)/2,因此平均情况、最好情况、最坏情况都是 O(n^2)
空间复杂度：O(1)
简单选择排序是一个不稳定的排序算法
7、堆排序
堆排序也是选择排序中的一种，是一种树形选择排序方法，特点是：在排序过程中，将 L[1…n]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲节点和孩子节点之间的内在关系，在当前无序区中选择关键字最大或最小的元素。
堆的定义如下：
1）L(i)<=L(2i)且 L(i)<=L(2i+1)【小根堆】或 L(i)>=L(2i)且 L(i)>=L(2i+1)【大根堆】
以大根堆为例，最大元素存放在根节点中，且对其任意非根节点，它的值小于或等于其双亲节点值；在小根堆中正好相反，根节点是最小元素。
堆排序分为两个步骤：1）创建初始堆；2）将堆顶元素与堆底元素交换位置，破坏堆的定义，重新调整堆，再重复这样的操作
细节：由于在堆排序中需要依靠数组下标来方便得到双亲节点与其子节点的关系，因此在调整堆的过程中这里数组 a[0]的作用只用来暂存元素，不存储实际元素的位置，牺牲一个数组元素空间位置，输出排序后的结果时从 1 到 n 输出，实际只有 n 个元素，但须创建 n+1 个元素的数组。
Java 代码如下：
import java.util.Scanner;
public class BigRootHeapSort {
public static void AdjustDown(int a[],int k,int length){
//函数 AdjustDown 将元素 k 向下进行调整成大根堆
a[0] = a[k];//a[0]暂存元素,仅作为替代值
for(int i=k2;i<=length;i=i2){
if(i<length && a[i]<a[i+1]){
i++;//取左右子节点中关键字较大的子节点的下标
}
if(a[0]>a[i])//被筛选节点小于双亲节点，筛选结束
break;
else{
a[k] = a[i];//将 a[i]调整到双亲节点上
k=i;//修改 k 值，以便继续向下筛选
}
}
a[k] = a[0];//被筛选节点值放入最终位置
}
//插入元素时，重新整理成大根堆，使用向上调整堆的算法
public static void AdjustUp(int a[],int k){
//参数 k 为向上调整的节点，也是堆的元素个数
a[0] =a[k];
int i = k/2;//若节点值大于双亲节点，则将双亲节点向下调，并继续向上比较
while(i>0 && a[i]<a[0]){//循环跳出条件
a[k] = a[i];//双亲节点往下调
k=i;
i = k/2;//继续向上比较
}
a[k] = a[0];//复制到最终位置
}
public static void BuildMaxHeap(int a[],int length){
//初始创建大根堆
for(int i=length/2;i>0;i–){//从 i=n/2 到 1 反复调整堆
AdjustDown(a,i,length);
}
}
public static void HeapSort(int a[],int length){
//进行堆排序
BuildMaxHeap(a,length);//初始创建大根堆
for(int i=length;i>1;i–){//n-1 趟的交换和建堆过程
int temp = a[i];//堆顶元素和堆底元素交换位置，删除元素时也是用同样的交换方法先将最大元素放在堆底，再取出堆底元素进行删除
a[i] = a[1];
a[1] = temp;
AdjustDown(a,1,i-1);//整理，把剩余的 i-1 个元素重新调整成堆
}
}
public static void main(String args[]){
//这里将 a[0]元素置为 0，便于大根堆的调整与交换，实际上存入了 n 个数但只会用到 n-1 个数
System.out.println(“请输入待排序的数据到数组中：”);
Scanner sc = new Scanner(System.in);
String str[] = sc.nextLine().split(” “);
int num[] = new int[str.length];
for(int i=0;i<num.length;i++){
num[i] = Integer.parseInt(String.valueOf(str[i]));
}
System.out.println(“形成大根堆后元素排列顺序为：”);
BuildMaxHeap(num,num.length-1);//调用大根堆创建过程算法排列数组元素
for(int i=1;i<num.length;i++)
System.out.print(num[i]+” “);
System.out.println(“\n 堆排序后的数组元素为：”);
HeapSort(num,num.length-1);//调用堆排序算法对数组元素排序
for(int i=1;i<num.length;i++)
System.out.print(num[i]+” “);
}
}
时间复杂度：在最好、最坏、平均情况下堆排序都为 O(nlogn)
空间复杂度：O(1)
堆排序是一个不稳定的排序算法
8、归并排序
归并排序有多路归并和 2-路归并，在内部排序中一般使用 2-路归并排序，在外部排序中使用多路归并排序
基本思路：归并排序与基于交换、选择等排序思想不一样，归并是将两个或两个以上的有序表组合成一个新的有序表。假定待排序表含有 n 个记录，可以看成是 n 个有序的子表，每个子表长度为 1，然后两两归并，得到 n/2（向上取整）个长度为 2 或 1 的有序表；在两两归并，如此反复，直到合并成一个长度为 n 的有序表为止。
递归形式的 2-路归并排序算法是基于分治的，其过程为：
分解：将含有 n 个元素的待排序表分成各含 n/2 个元素的子表，采用 2-路归并排序算法对两个子表递归地进行排序；
合并：合并两个已排好序的子表得到排序结果；
Java 代码如下：
import java.util.Scanner;
public class MergeIntoSort {
public static void Merge(int a[],int low,int mid,int high){
//表 a 的两段 a[low…mid]和 a[mid+1…high]各自有序，将它们合并成一个有序表
//设立铺助数组 b[]
int b[] = new int[a.length];
for(int i=low;i<=high;i++){
b[i]=a[i];//将 a 中所有元素复制到 b 数组中
}
int i,j,k;
for(i=low,j=mid+1,k=i;i<=mid&&j<=high;k++){
if(b[i]<=b[j])//比较 b 数组左右两段中的元素
a[k] = b[i++];//小的数复制到 a 数组中
else//不能改为 if(b[i]>b[j])
a[k] = b[j++];
}
while(i<=mid)
a[k++] = b[i++];//若前段未复制完，直接复制
while(j<=high)
a[k++] = b[j++];//若后段未复制完，直接复制
}
//使用递归形式的分治法进行归并排序
public static void MergeSort(int a[],int low,int high){
if(low<high){
int mid = (low+high)/2;//从中间划分两个子序列
MergeSort(a,low,mid);//对左侧子序列进行递归排序
MergeSort(a,mid+1,high);//对右侧子序列进行递归排序
Merge(a,low,mid,high);//划分之后归并
}
}
public static void main(String args[]){
System.out.println(“请输入待排序的数据到数组中：”);
Scanner sc = new Scanner(System.in);
String str[] = sc.nextLine().split(” “);
int num[] = new int[str.length];
for(int i=0;i<num.length;i++){
num[i] = Integer.parseInt(String.valueOf(str[i]));
}
//调用归并排序算法进行排序
MergeSort(num,0,num.length-1);
System.out.println(“排序后的结果为：”);
for(int i=0;i<num.length;i++){
System.out.print(num[i]+” “);
}
}
}
时间复杂度：平均、最好、最坏情况下都为 O(nlogn)
空间复杂度：需要 n 个单元的铺助空间，因此为 O(n)
2-路归并排序算法是一个稳定的排序算法；
注：一般而言，对于 N 个元素进行 k-路归并排序时，排序的趟数 m 满足 k^m=N,可得 m=logk(N)，又考虑到 m 为整数，所以 m=|logk(N)|(向上取整)
9、基数排序
基本思路：
基数排序不是基于比较进行排序的，而是采用多关键字排序思想（即基于关键字各位的大小进行排序），借助“分配”和“收集”两种操作对单逻辑关键字进行排序。基数排序又分为最高位优先排序（MSD）和最低位优先排序(LSD)。
以三位数的元素为例，可将元素看作为（K^3,K^2,K^1）组合，K^3 是百位上的数字，K^2 是十位上的数字，K^1 是个位上的数字，使用最高位优先排序方法，在排序过程中，首先根据百位上的数字（K^3）进行排序，按各元素在百位上的取值，分配到各个子序列（称为桶）中，然后然后再按桶的编号，逐桶进行递归地基数排序，在每个桶中，子序列的规模已经大大减少，同时桶中所有元素在百位上的数字取值相同，这时，按各元素的十位上的数字（K^2）取值继续进行桶式分配，之后还对各个子桶中的元素按个位（K^1）进行分配，从而使得待排序序列所有元素排好序。
代码如下：
各个排序算法比较及其适用范围说明：
各种排序算法的使用范围总结：
(1)当数据规模较小的时候，可以使用简单的排序算法如直接插入排序或直接选择排序。
(2)当待排序表的初始状态已经基本有序时，可以使用直接插入排序（希尔排序）或冒泡排序。
当数据规模较大时，应采用时间复杂度为 O(nlogn)的排序方法：快速排序、堆排序、归并排序。
(3)当数据规模较大时，应用速度快的排序算法。可以考虑快速排序。当记录随机分布的时候，快排的平均时间最短，但可能出现最坏的情况，这时候的时间复杂度是O(n^2)，且递归深度为n，所需的栈空间为O(n)。
(4)堆排序不会出现快排那样的最坏情况，且堆排序所需的辅助空间比快排要少。但这两种算法都不是稳定的，若要求排序时稳定，可以考虑用归并排序。
(5)归并排序可以用于内部排序，也可以用于外部排序。在外部排序时，通常采用多路归并，并且通过解决长顺串的合并，产生长的初始串，提高主机与外设并行能力等措施，以减少访问外存次数，提高外排序的效率。
（6）当数据规模很大，记录的关键字位数较少且可以分解时，采用基数排序较好。
