数据结构中常用的几种排序算法

“来同学，咱们做个题吧，写个最基本的快排。。。”，校招季的各种面试中相信大家经常听到类似的话语。排序是作为数据结构中比较重要的一部分来讲，今天笔者又拿出来当年的数据结构课本进行了一下总结，并对几个重要的排序算法进行了实现。

排序的基本概念

排序： 重新排列表中的元素，使表中的元素按照关键字递增或者递减的过程。
算法的稳定性： 如果在排序序列中存在多个具有相同关键字的元素，在经过排序后，这些记录的相对次序依然保持不变，则称这种排序算法是稳定的，否则称之为不稳定的。
内部排序： 在排序期间元素全部存放在内存中的排序。
外部排序： 在排序期间无法全部同时存放在内存中，必须在排序过程中根据要求不断地在内、外存之间移动的排序。

下图为排序的逻辑导图：

各种排序算法的比较

下面进行比较的排序算法主要针对内部排序，外部排序此处暂且不做讨论。一般内部排序算法在执行过程中主要是基于以下两种操作来进行的：比较和移动，通过比较两个关键字的大小，确定元素的前后关系，然后通过移动元素达到有序。此处需要注意的是：基数排序是不需要进行比较的

插入排序

插入排序是一种简单直观的排序方法，其思想在于每次将一个待排序的记录，按其关键字的大小插入到前面已经排序好的子序列中，直到全部记录插入完成。插入排序又分为：直接插入排序，折半插入排序，希尔排序。

直接插入排序

直接插入排序的思想：为了将arr[i]插入到arr[0…i-1]中,需要依次执行以下操作：

• 查找出arr[i]在arr[0…i-1]中的插入位置k
• 将arr[k…i-1]中所有元素全部后移一个位置
• 将arr[i]复制到arr[k]

为了实现整个排序过程，只要从数组的第一个元素即arr[1]到arr[n-1]执行n-1次上述操作即可。
以下是使用java实现的插入排序过程：

public static void insertSort(int arr[]){
	int i,j;
	for(i=1;i<arr.length;i++){//依次将arr[1]-arr[n-1]插入到前面已排序序列
		if(arr[i]<arr[i-1]){
			int temp = arr[i];
			for(j=i-1;temp<arr[j];j--){
				arr[j+1] = arr[j];
			}
			arr[j+1] = temp;
		}
	}
	print(arr);
}

直接插入排序算法的性能分析：
空间效率：仅仅使用了常数个辅助单元，因此空间复杂度为O(1)
时间效率：在排序过程中，向有序的序列中插入元素的操作进行了n-1次，每次操作都分为比较和移动两个操作，比较的次数和移动的次数取决于待排序序列的初始状态。最好情况下，数组整体是有序的，插入元素的过程仅仅需要比较，并不需要移动元素，因此最坏情况下时间复杂度为O(n)。最坏情况下，数组的元素顺序正好和排序结果的元素顺序相反，此时每次插入都需要比较和移动。平均情况下，考虑待排序数组中的元素是随机的，时间复杂度为O(n^2)。
稳定性：由于每次插入元素都是先比较在移动，因此不会出现相同元素相对位置发生变化的情况。因此直接插入排序算法是稳定的。

折半插入排序

折半插入排序在直接插入排序算法的基础做了改进。折半插入排序将整个排序过程分为两个过程：通过折半查找找出待插入的位置，然后统一移动元素。

以下是使用java实现的折半插入排序过程：

public static void insertSort2(int arr[]){
	int i,j,low,high,mid;
	for(i = 1;i<arr.length;i++){
		int temp = arr[i];
		low = 0;
		high = i-1;
		while(low<=high){
			mid=(low+high)/2;
			if(arr[mid]>temp){
				high=mid-1;
			}else{
				low=mid+1;
			}
		}
		for(j=i-1;j>=high+1;j--){
			arr[j+1]=arr[j];
		}
		arr[high+1]=temp;
	}
	print(arr);
}

折半插入排序算法性能分析：
折半插入排序算法相对于直接插入排序算法来说仅仅是减少了元素的比较次数，元素的移动次数并没有改变，因此折半插入的时间复杂度仍为O(n^2),空间复杂度为O(1),折半插入排序算法是稳定的。

希尔排序

希尔排序又叫缩小增量排序，其基本思想是：先将排序表按照一定增量分为若干个待排序的字表，分别进行直接插入排序，当整个表中元素已呈”基本有序”时，再对整体进行一次直接插入排序。

以下是java实现的希尔排序过程：

public static void shellSort(int arr[]){
   	int i,j,d,len = arr.length;
   	for(d=len/2;d>=1;d=d/2){
   		for(i=d+1;i<len;i++){
   			if(arr[i]<arr[i-d]){
   				int temp=arr[i];
   				for(j=i-d;j>0&&temp<arr[j];j-=d){
   					arr[j+d]=arr[j];
   				}
   				arr[j+d]=temp;
   			}
   		}
   	}
   	print(arr);
   }

希尔排序算法的性能分析：
空间效率：使用了常数个辅助单元，空间复杂度为O(1)
时间效率：最坏情况下希尔排序的时间复杂度为O(n^2)
稳定性：希尔排序算法不是一个稳定的排序算法

小结

直接插入排序和折半插入排序适用于基本有序的排序表和数据量不大的排序表。因为其中涉及到大量的移动元素，在数据量较小的时候，虽然两者的时间复杂度都为O(n^2)，折半插入排序往往能表现更好的性能。

交换排序

交换排序的基本思想在于根据序列中两个元素的比较结果对换这两个元素在序列中的位置。交换排序有很多种实现算法，此处只讨论冒泡排序和快速排序。其中快速排序是重点内容。

冒泡排序

冒泡排序是一种比较简单排序算法。其基本思想是：在一个长为n的待排序表中，从后向前（也可以从前向后）两两比较相邻的元素，如果arr[i-1]>arr[i]时，则交换它们，直到序列比较完，这位一次冒泡过程。一次冒泡的结果就是将最小的元素交换到待排序序列的第一个位置。下一趟冒泡的过程，前一趟已经确定的最小元素不参与比较，待排序序列中就减少了一个元素。每一次冒泡都将待排序序列中的最小元素放到了最终位置。
以下是java实现的冒泡排序算法：

public static void bubbleSort(int arr[]){
	int i,j,len=arr.length;
	for(i=0;i<len-1;i++){
		boolean flag=false;
		for(j=len-1;j>i;j--){
			if(arr[j-1]>arr[j]){
				int temp = arr[j-1];
				arr[j-1]=arr[j];
				arr[j]=temp;
				flag=true;
			}
		}
		if(flag){
			print(arr);
			return;
		}
		print(arr);
	}
}

冒泡排序算法的性能分析：
空间效率：仅使用了常数个辅助单元，因此空间复杂度为O(1)
时间效率：最好情况下，待排序序列基本有序，比较次数为n-1,移动次数为0，时间复杂度为O(n),最坏情况下，初始序列为逆序，需要进行n-1趟冒泡，每次冒泡进行n-i次比较，这种情况下时间复杂度为O(n^2)。平均情况下时间复杂度为O(n^2)。
稳定性：冒泡排序是一个稳定的排序算法

快速排序

快速排序是对冒泡排序的一个改进，其基本思想是基于分治策略，在待排序序列中任取一个元素p作为基准元素，通过一次排序将待排序表氛围独立的两个部分，arr[0…k-1]和arr[k+1…n-1],其中前者中的元素均小于p,后者中的元素均大于p，p则放在其最终位置arr[k]中，这个过程为一次快速排序。然后对两个子序列分别递归的进行快速排序，直至每个部分中只有一个元素或者为空为止。
以下是java实现快速排序算法的过程：

//快速排序
public static void quickSort(int arr[],int low,int high){
	if(low<high){
		int p = Partition(arr,low,high);
		quickSort(arr,low,p-1);
		quickSort(arr,p+1,high);
	}

}
public static int Partition(int arr[],int low,int high){
	int  p =arr[low];
	while(low<high){
		while(low<high&&arr[high]>=p) high--;
		arr[low]=arr[high];
		while(low<high&&arr[low]<=p) low++;
		arr[high]=arr[low];
	}
	arr[low]=p;
	return low;
}

快速排序算法的关键在于划分操作。划分操作算法也影响着快速排序算法的性能。上面算法中的划分操作主要是假设每次总是以当前表中第一个元素作为枢纽值对表进行划分，表中比枢纽值大的元素向右移动，比枢纽值小的向左移动，从而使得在一次划分操作之后，表中的元素被枢纽值一分为二。
快速排序算法的性能分析：
空间效率：快速排序算法借助了递归来实现，因此需要一个递归工作栈来保存递归过程中的信息。最好情况下为log(n+1),最坏情况下需要进行n-1次递归调用，因此为最坏情况下为O(n),平均情况下，为O(log(n))。
时间效率：快速排序算法的时间效率和划分操作是否对称有关，因此时间效率的关键在于划分算法的实现。最坏情况下即待排序表基本有序或逆序时，此时时间复杂度为O(n^2)。最好情况下，时间复杂度为O(nlog(n))。
稳定性：快速排序算法不是一个稳定的排序算法。

选择排序

选择排序的基本思想是在每一趟的排序的过程中，在剩下的元素中找出最小的元素放在该趟排序的位置上，例如第i趟排序，则在arr[i+1,n-1]中找出最小的元素放在arr[i]中。经过n-1趟排序就可以完成整个排序过程。

简单选择排序

简单选择排序的思想就是以上选择排序的一个实现。
以下为java实现的简单选择排序算法：

public static void selectSort(int arr[]){
  	int i,j,min;
  	for(i=0;i<arr.length-1;i++){
  		min=i;
  		for(j=i+1;j<arr.length;j++){
  			if(arr[j]<arr[min]){
  				min=j;
  			}
  		}
  		if(min!=i){
  			int temp=arr[i];
  			arr[i]=arr[min];
  			arr[min]=temp;
  		}
  	}
  	print(arr);
	}

简单选择排序算法性能分析：
空间效率：仅使用了常数个辅助单元，因此空间复杂度为O(1)。
时间效率：元素之间的比较次数与初始状态无关，始终是n(n-1)/2,因此时间复杂度为O(n^2)。
稳定性：简单选择排序不是一个稳定的排序算法。

堆排序

堆排序是一种树形选择排序方法，其基本思想就是将待排序序列看成一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲节点与孩子节点之间的关系，在当前无序区中选择最大或者最小的元素。

大顶堆：在待排序序列中L[1…n]中，如果该序列满足L(i)>=L(2i)且L(i)>=L(2i+1)，则称该种情况组成的堆为大顶堆。
小顶堆：在待排序序列中L[1…n]中，如果该序列满足L(i)<=L(2i)且L(i)<=L(2i+1)，则称该种情况组成的堆为小顶堆。

在大顶堆中，根元素为最大的元素，小顶堆中，根节点是最小元素。

堆排序的基本思想：堆排序的关键在于构建初始堆。n个节点的完全二叉树，最后一个节点是第(n/2)个节点的孩子。对第(n/2)个节点为根的子树按照大顶堆或者小顶堆相应的特点筛选，使该子树成为堆。之后向前依次对第(n/2-1)个节点到第1个节点为根的子树依次筛选。以大顶堆为例，判断该节点值是否大于其左右孩子节点的值，如果不是，则将左右孩子节点中最大的值与该节点进行交换，交换后如果破坏了下一级的堆，则继续按照上述规则构造下一级的堆，直到该节点为根的子树构成堆为止。反复利用上述调整堆的方法建堆，直到根节点。
使用堆排序时，首先将L[1…n]中n个元素构建初始堆，大顶堆中，堆顶元素就是最大值。输出堆顶元素后，将堆底元素送入堆顶，此时根节点已不满足大顶堆的性质，此时按照调整规则将以根节点为父节点的子树调整，使其继续保持大顶堆的性质，再输出堆顶元素，重复循环，直到堆中仅剩下一个元素为止。

以下是java实现的堆排序算法：

//堆排序
   public static void HeapSort(int []arr,int len){
   	buildHeap(arr,len);
   	for(int i=len-1;i>=0;i--){
   		int temp=arr[i];
   		arr[i]=arr[0];
   		arr[0]=temp;
   		AdjustDown(arr,0,i);
   	}
   	print(arr);

   }
   public static void buildHeap(int arr[],int len){
   	for(int i=len/2;i>=0;i--){
   		AdjustDown(arr, i, len);
   	}

   }
   public static void AdjustDown(int arr[],int k,int len){
   	int temp = arr[k];
   	for(int i = 2*k;i<len;i*=2){
   		if(i<len-1&&arr[i]<arr[i+1]){
   			i++;
   		}
   		if(temp>=arr[i]) break;
   		else{
   			arr[k]=arr[i];
   			k=i;
   		}
   	}
   	arr[k]=temp;
   }

堆排序算法的性能分析如下：
空间效率：仅使用了常数个辅助单元，因此空间复杂度为O(1)。
时间效率：建堆时间为O(n)，之后有n-1次向下调整操作，每次调整的时间复杂度为O(h),h为子树的高度。因此在最好、最坏以及平均情况下，堆排序的时间复杂度为O(nlogn)。
稳定性：堆排序算法是一种不稳定的排序算法。

归并排序和基数排序

归并排序

归并排序的基本思想：将两个或两个以上的有序表组合成一个新的有序表。如果待排序表中有n个记录，则可以看成是n个有序的子表，每个字表的长度为1，然后两两归并，得到n/2个长度为2或1的有序表，之后再进行两两归并，直到合并成一个长度为n的有序表为止。这称之为2-路归并排序。
以下是java实现的归并排序算法：

//归并排序
  public static int []temp = new int[n+1];
  public static void merge(int []arr,int low,int mid,int high){
  	int i,j,k;
  	for(k=low;k<=high;k++){
  		temp[k]=arr[k];
  	}
  	for(i=low,j=mid+1,k=i;i<=mid&&j<=high;k++ ){
  		if(temp[i]<=temp[j]){
  			arr[k]=temp[i++];
  		}else{
  			arr[k]=temp[j++];
  		}
  	}
  	while(i<=mid) arr[k++]=temp[i++];
  	while(j<=high) arr[k++]=temp[j++];
  }
  public static void mergeSort(int arr[],int low,int high){
  	if(low<high){
  		int mid=(low+high)/2;
  		mergeSort(arr,low,mid);
  		mergeSort(arr, mid+1, high);
  		merge(arr,low,mid,high);
  	}
  }

2-路归并排序算法的性能分析如下：
空间效率：因为使用了n个单位的辅助空间，因此归并排序的空间复杂度为O(n)。
时间效率：每一趟归并的时间复杂度为O(n),需要进行(logN)次归并，因此算法的时间复杂度为O(nlogn)。
稳定性：2-路归并排序算法是一个稳定的排序算法。

基数排序

基数排序不是一种基于比较和交换的排序算法，而是采用多关键字排序思想，借助“分配”和“收集”两种操作对单逻辑关键字进行排序。基数排序分为最高位优先排序和最低位优先排序。

总结

上述部分给出了各种排序算法的基本思想及其实现。下表为各种排序算法的性质：