一、几种常见的排序算法性能比較
| 排序算法 | 最好时间 | 平均时间 | 最坏时间 | 辅助内存 | 稳定性 | 备注 |
|---|---|---|---|---|---|---|
| 简单选择排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 不稳定 | n小时较好 |
| 直接插入排序 | O(n) | O(n^2) | O(n^2) | O(1) | 稳定 | 大部分已有序的较好 |
| 冒泡排序 | O(n) | O(n^2) | O(n^2) | O(1) | 稳定 | n小时较好 |
| 希尔排序 | O(n) | O(nlogn) | O(n^s), s∈(1,2) | O(1) | 不稳定 | s是所选分组 |
| 高速排序 | O(nlogn) | O(nlogn) | O(n^2) | O(logn) | 不稳定 | n大时较好 |
| 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不稳定 | n大时较好 |
| 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 稳定 | n大时较好 |
注：稳定——所有相等的数经过排序之后，仍能保持它们在排序之前的相对位置关系。
二、常见算法的实现（java）
1、选择排序（Selection Sort）
选择排序的基本思想是对待排序的记录序列进行n-1遍的处理，第i遍处理是将L[i..n]中最小者与L[i]交换位置。这样，经过i遍处理之后，前i个记录的位置已经是正确的了。
public class selectSort {
public static void selectSort(int[] a){
int i,j;
for (i=0;i<a.length;i++){
for (j=i+1;j<a.length;j++){
if (a[j]<a[i]){
int temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
}
}
public static void main(String args[]){
int[] a={5,4,9,8,7,6,0,1,3,-5};
selectSort(a);
for(int i=0;i<a.length;i++){
System.out.print(a[i]+" ");
}
System.out.println();
}
}２、插入排序（Insertion Sort）
插入排序的基本思想是，经过i-1遍处理后,L[1..i-1]己排好序。第i遍处理仅将L[i]插入L[1..i-1]的适当位置，使得L[1..i]又是排好序的序列。
要达到这个目的。我们能够用顺序比較的方法。
首先比較L[i]和L[i-1]，假设L[i-1]≤ L[i]。则L[1..i]已排好序，第i遍处理就结束了；否则交换L[i]与L[i-1]的位置，继续比較L[i-1]和L[i-2]。直到找到某一个位置j(1≤j≤i-1)，使得L[j] ≤L[j+1]时为止。图1演示了对4个元素进行插入排序的过程，共须要(a),(b),(c)三次插入。
public class insertSort {
public static void insertSort(int[] a){
if (a!=null){
for (int i=1;i<a.length;i++){
int temp=a[i],j=i;
if (a[j-1]>temp){
while(j>=1&&a[j-1]>temp){
a[j]=a[j-1];
j--;
}
}
a[j]=temp;
}
}
}
public static void main(String args[]){
int[] a={5,4,9,8,7,6,0,1,3,2};
insertSort(a);
for(int i=0;i<a.length;i++){
System.out.print(a[i]+" ");
}
System.out.println();
}
}
３、冒泡排序（Bubble Sort）
冒泡排序方法是最简单的排序方法。这样的方法的基本思想是，将待排序的元素看作是竖着排列的“气泡”。较小的元素比較轻。从而要往上浮。
在冒泡排序算法中我们要对这个“气泡”序列处理若干遍。所谓一遍处理，就是自底向上检查一遍这个序列，并时刻注意两个相邻的元素的顺序是否正确。假设发现两个相邻元素的顺序不正确。即“轻”的元素在以下，就交换它们的位置。显然，处理一遍之后。“最轻”的元素就浮到了最高位置。处理二遍之后，“次轻”的元素就浮到了次高位置。
在作第二遍处理时，由于最高位置上的元素已是“最轻”元素。所以不必检查。
一般地。第i遍处理时。不必检查第i高位置以上的元素，由于经过前面i-1遍的处理，它们已正确地排好序。
public class bubbleSort {
public static void bubbleSort(int[] a){
for (int i=0;i<a.length;i++){
for (int j=0;j<a.length-1;j++){
if (a[j]>a[j+1]){
int temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
}
public static void main(String args[]) {
int[] a = {5, 4, 9, 8, 7, 6, 0, 1, 3, 2};
bubbleSort(a);
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
System.out.println();
}
}
４、希尔排序（Shell Sort）
在直接插入排序算法中，每次插入一个数，使有序序列仅仅添加1个节点。而且对插入下一个数没有提供不论什么帮助。假设比較相隔较远距离（称为增量）的数，使得数移动时能跨过多个元素，则进行一次比較就可能消除多个元素交换。D.L.shell于1959年在以他名字命名的排序算法中实现了这一思想。
算法先将要排序的一组数按某个增量d分成若干组，每组中记录的下标相差d.对每组中所有元素进行排序，然后再用一个较小的增量对它进行。在每组中再进行排序。当增量减到1时，整个要排序的数被分成一组。排序完毕。
public class shellSort {
public static void shellSort(int[] array){
int len=array.length;
for(int h=len/2;h>0;h=h/2){//步长为h
for (int i=h;i<len;i++){
int temp=array[i];
int j;
for (j=i-h;j>=0;j-=h){//相隔h个常量。跳跃式移动。使得排序效率提高
if (temp==array[j]){
array[j+h]=array[h];
}else break;
}
array[j+h]=temp;
}
}
}
public static void main(String args[]){
int[] a={5,4,9,8,7,6,0,1,3,2};
shellSort(a);
for(int i=0;i<a.length;i++){
System.out.print(a[i]+" ");
}
System.out.println();
}
}５、高速排序（Ｑuick Sort）
高速排序是对冒泡排序的一种本质改进。
它的基本思想是通过一趟扫描后，使得排序序列的长度能大幅度地降低。
在冒泡排序中。一次扫描仅仅能确保最大数值的数移到正确位置，而待排序序列的长度可能仅仅降低1。高速排序通过一趟扫描，就能确保某个数（以它为基准点吧）的左边各数都比它小，右边各数都比它大。
然后又用相同的方法处理它左右两边的数，直到基准点的左右仅仅有一个元素为止。
public class quickSort {
public static void quickSort(int[] array,int low,int high) {
if(low < high){
int privotLoc = partition(array, low, high); //将表一分为二
quickSort(array,low,privotLoc -1); //递归对低子表递归排序
quickSort(array,privotLoc + 1,high); //递归对高子表递归排序
}
}
public static int partition(int a[], int low, int high) {
int privotKey = a[low]; //基准元素
while(low < high){ //从表的两端交替地向中间扫描
while(low < high && a[high] >= privotKey)
--high; //从high 所指位置向前搜索。至多到low+1 位置。将比基准元素小的交换到低端
swap(a,low,high);
while(low < high && a[low] <= privotKey )
++low;
swap(a,low,high);
}
return low;
}
public static void swap(int[] a, int i,int j) {
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
public static void main(String args[]){
int[] a={5,4,9,8,7,6,0,1,3,2};
quickSort(a,0,a.length-1);
for(int i=0;i<a.length;i++){
System.out.print(a[i]+" ");
}
System.out.println();
}
}
６、堆排序（Ｈeap Sort）
堆排序是一种树形选择排序，在排序过程中，将A[n]看成是全然二叉树的顺序存储结构。利用全然二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素。
/**
* 堆排序
*
* 首先使用建立最大堆的算法建立好最大堆，
* 然后将堆顶元素（最大值）与最后一个值交换，
* 同一时候使得堆的长度减小1 ，调用保持最大堆性质的算法调整。
* 使得堆顶元素成为最大值，此时最后一个元素已被排除在外
*/
public class heapSort {
private static int heapSize;//元素个数
private static void maxHeapify( int[] array , int index ){
int left = 2*index;//左孩子
int right = 2*index+1;//右孩子
int largest;
if( left < heapSize && array[ index ] < array[ left ]){
largest = left;
}else{
largest = index;
}
if( right < heapSize && array[ right ] > array[ largest ]){
largest = right;
}
if( largest == index ){
return ;
} else {
int temp = array[ index ];
array[ index ] = array[ largest ];
array[ largest ] = temp;
maxHeapify( array, largest );
}
}
/**
* 建立最大堆。在数据中，array.length/2+1一直到最后的元素都是叶子元素。
* 因此从其前一个元素開始，一直到第一个元素，反复调用maxHeapify函数，使其保持最大堆的性质
* @param array
*/
private static void buildMaxHeap(int[] array){
// 找出最小元素,并将其置于array[0]
int min = array[0];
for(int i = 1 ; i < array.length ; i++ ){
if( min > array[i] ){
min = array[i];
array[i] = array[0];
array[0] = min;
}
}
for( int i = array.length / 2 ; i >= 1; i-- ){
maxHeapify( array , i );
}
}
/**
* 堆排序:
*/
public static void heapSort( int[] array ){
buildMaxHeap( array );
for(int i = array.length - 1 ; i >= 2 ; i--){
int temp = array[1];
array[1] = array[i];
array[i] = temp;
heapSize--;
maxHeapify( array , 1 );
}
}
public static void main(String args[]){
int[] a={5,4,9,8,7,6,0,1,3,2};
heapSize = a.length;
heapSort(a);
for(int i=0;i<a.length;i++){
System.out.print(a[i] + " ");
}
System.out.println();
}
}
７、归并排序（Ｍerge Sort）
设有两个有序（升序）序列存储在同一数组中相邻的位置上，最好还是设为A[l..m]，A[m+1..h]，将它们归并为一个有序数列，并存储在A[l..h]。
public class mergeSort {
public static void MergeSort(int[] array,int p,int r){
if (p<r){
int q=(p+r)/2;
MergeSort(array,p,q);
MergeSort(array,q+1,r);
Merge(array,p,q,r);
}
}
public static void Merge(int[] array,int p,int q,int r){
int n1=q-p+1;
int n2=r-q;
int[] L=new int[n1];
int[] R=new int[n2];
for (int i=0;i<n1;i++){
L[i]=array[p+i];
}
for (int i=0;i<n2;i++){
R[i]=array[q+1+i];
}
int i,j,k=p;
for (i=0,j=0;i<n1&&j<n2;k++){
if (L[i]<R[j]){
array[k]=L[i];
i++;
}else{
array[k]=R[j];
j++;
}
}
if (i<n1){
for (j=i;j<n1;j++,k++)
array[k]=L[j];
}
if (j<n2){
for (i=j;i<n2;i++,k++)
array[k]=R[i];
}
}
public static void main(String args[]) {
int[] a = {5, 4, 9, 8, 7, 6, 0, 1, 3, 2};
MergeSort(a,0,a.length-1);
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
System.out.println();
}
}