排序算法總結及java實作

十種排序算法的基本特性：

排序算法	平均時間複雜度	最好情況	最壞情況	空間複雜度	排序方式	穩定性
快速排序	Ο（nlogn)	Ο（nlogn)	Ο（n2)	Ο（logn)	in-place	不穩定
歸并排序	Ο（nlogn)	Ο（nlogn)	Ο（nlogn)	Ο（n)	out-place	穩定
堆排序	Ο（nlogn)	Ο（nlogn)	Ο（nlogn)	Ο（1)	in-place	不穩定
shell排序	Ο（nlogn)	Ο（nlog2n)	Ο（nlog2n)	Ο（1)	in-place	不穩定
插入排序	Ο（n2)	Ο（n)	Ο（n2)	Ο（1)	in-place	穩定
冒泡排序	Ο（n2)	Ο（n)	Ο（n2)	Ο（1)	in-place	穩定
選擇排序	Ο（n2)	Ο（n2)	Ο（n2)	Ο（1)	in-place	不穩定
計數排序	Ο（n+k)	Ο（n+k)	Ο（n+k)	Ο（k)	out-place	穩定
桶排序	Ο（n+k)	Ο（n+k)	Ο（n2)	Ο（n+k)	out-place	穩定
基數排序	Ο（n*k)	Ο（n*k)	Ο（n*k)	Ο（n+k)	out-place	穩定

*穩定性：多個相同的值的相對位置在算法結束時是否産生變動。

一、快速排序

• 快速排序由C. A. R. Hoare在1960年提出。它的基本思想是：通過一趟排序将要排序的資料分割成獨立的兩部分，其中一部分的所有資料都比另外一部分的所有資料都要小，然後再按此方法對這兩部分資料分别進行快速排序，整個排序過程可以遞歸進行，以此達到整個資料變成有序序列。

• 原理：

  設要排序的數組是A[0]……A[N-1]，首先任意選取一個資料（通常選用數組的第一個數）作為關鍵資料，然後将所有比它小的數都放到它左邊，所有比它大的數都放到它右邊，這個過程稱為一趟快速排序。

  1）設定兩個變量i、j，排序開始的時候：i=0，j=N-1；

  2）以第一個數組元素作為關鍵資料，指派給key，即key=A[0]；

  3）從j開始向前搜尋，即由後開始向前搜尋(j–)，找到第一個小于key的值A[j]，将A[j]和A[i]的值交換；

  4）從i開始向後搜尋，即由前開始向後搜尋(i++)，找到第一個大于key的A[i]，将A[i]和A[j]的值交換；

  5）重複第3、4步，直到i=j； (3,4步中，沒找到符合條件的值，即3中A[j]不小于key,4中A[i]不大于key的時候改變j、i的值，使得j=j-1，i=i+1，直至找到為止。找到符合條件的值，進行交換的時候i， j指針位置不變。另外，i==j這一過程一定正好是i+或j-完成的時候，此時令循環結束）。

• 變種：1）随機化快排       2）平衡快排      3）外部快排

實作：

//遞歸法
private static int quickOne(int data[],int left,int right)
	{
		if(data==null) return -1;
		int key=data[left];
		while(left<right)
		{
			while(left<right && data[right]>=key) right--;
			data[left]=data[right];
			while(left<right && data[left]<key) left++;
			data[right]=data[left];
		}
		data[left]=key;
		return left;
	}
	private static void quickTwo(int data[],int left,int right)
	{
		if(data==null) return ;
		int mid=quickOne(data,left,right);
		if(left<mid-1) quickTwo(data,0,mid-1);
		if(mid+1<right) quickTwo(data,mid+1,right);
	}
	public static void quickSort1(int data[])
	{
		if(data==null) return ;
		quickTwo(data,0,data.length-1);
	}
           

public static void quickSort2(int data[])
	{
		if(data==null) return ;
		ArrayQueue queue = new ArrayQueue();
		queue.inQueue(0);              //最開始序列的首下标為0
		queue.inQueue(data.length-1);    //最開始序列的尾下标為傳入數組的最後一個元素下表
		while(!queue.isEmpty())
		{
			int left=queue.outQueue();
			int right=queue.outQueue();
			int mid=quickOne(data,left,right);
			if(left<mid-1)     //左序列有兩個以上元素時，将左序列的首尾下标入隊
			{
				queue.inQueue(left);
				queue.inQueue(mid-1);
			}
			if(mid+1<right)     //右序列有兩個以上元素時，将右序列的首尾下标入隊
			{
				queue.inQueue(mid+1);
				queue.inQueue(right);
			}
		}
	}
           

二、歸并排序

• 歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。将已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。

• 原理：

  第一步：申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合并後的序列

  第二步：設定兩個指針，最初位置分别為兩個已經排序序列的起始位置

  第三步：比較兩個指針所指向的元素，選擇相對小的元素放入到合并空間，并移動指針到下一位置

  重複步驟3直到某一指針超出序列尾

  将另一序列剩下的所有元素直接複制到合并序列尾

• 歸排一般用于對總體無序，但是各子項相對有序的數列
• 改進歸并排序在歸并時先判斷前段序列的最大值與後段序列最小值的關系再确定是否進行複制比較。

三、堆排序

四、Shell排序

• 希爾排序是一種快速排序法，又稱作縮小增量排序

• 基本思想：

  　　不斷把待排序的對象分成若幹個小組，對同一小組内的對象采用直接插入法排序，當完成了所有對象都分在一個組内的排序後，排序過程結束。每次比較指定間距的兩個資料項，若左邊的值小于右邊的值，則交換它們的位置。間距d按給定公式減少： di+1 =（di +1）/2 ，直到d等于1為止。

實作：

public static void shellSort(int data[])
	{
		if(data==null) return ;
		int k=data.length/2+1;
		while(k>0)
		{
			for(int i=0;i<data.length-k;i++)
			{
				if(data[i]>data[i+k])
				{
					int t=data[i];
					data[i]=data[i+k];
					data[i+k]=t;
				}			
			}
		k--;
		}
	}
           

五、插入排序

• 原理：通過建構有序序列，對于未排序資料，在已排序序列中從後向前掃描，找到相應位置并插入。

• 具體算法：

  從第一個元素開始，該元素可以認為已經被排序

  取出下一個元素，在已經排序的元素序列中從後向前掃描

  如果該元素（已排序）大于新元素，将該元素移到下一位置

  重複上述步驟，直到找到已排序的元素小于或者等于新元素的位置

  将新元素插入到該位置後

• 變種：

  二分查找插入排序：查找插入位置部分使用二分查找法

  僞冒泡插入排序：插入部分使用冒泡排序法

實作：

//普通插入排序
	public static void insertionSort(int data[])
	{
		if(data==null) return ;
		for(int i=1;i<data.length;i++)
		{
			int j=0;
			int t=data[i];
			for(j=0;j<i;j++)			
				if(t<=data[j]) break;   //将資料插入第一個比它大的數之前
			for(int k=i;k>j;k--)
			{
				data[k]=data[k-1];
			}
			data[j]=t;				
			
		}
	}
           

//折半插入排序
	public static void binarySort(int data[])
	{
		if(data==null) return ;
		for(int i=1;i<data.length;i++)
		{
			int key=data[i];
			int low = 0;
	        int high = i-1;
			for(int j=0;j<i;j++)
			{
				while (low<=high) 
				{
		        	int mid = (low+high)/2;
		            if(data[mid]== key)
		            {
		            	high=mid;
		            	break;
		            }     
		            else if (data[mid] < key) low = mid+1;
		            else if (data[mid] > key) high = mid-1;
		        }				
			}
			high++;
			for(int k=i;k>high;k--)
				data[k]=data[k-1];
			data[high]=key;	
		}		       
	}
           

//僞冒泡插入排序
public static void insertionSort2(int data[])
	{
		if(data==null) return;
		for(int i=1;i<data.length;i++)
		{
			for(int j=i;j>0;j--)
			{
				if(data[j]<data[j-1])        //僞冒泡交換
				{
					int t=data[j];
					data[j]=data[j-1];
					data[j-1]=t;
				}
				else break;
			}	
		}
	}
           

六、冒泡排序

• 算法描述：
  • 比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
  • 對每一對相鄰元素做同樣的工作，從開始第一對到結尾的最後一對。是以，最後的元素為最大的數。
  • 針對所有的元素重複以上的步驟，除了最後一個。
  • 重複上述過程，直至所有元素有序

實作：

public static void bobSort(int data[])
	{
		if(data==null) return;   //保證程式的健壯性！
		
		int len = data.length-1;
		while(len>0){		
			for(int i=0;i<len;i++)
			{
				if(data[i]>data[i+1])
				{
					int t = data[i];
					data[i] = data[i+1];
					data[i+1] = t;
				}
			}
			len--;
		}
	}
           

七、選擇排序

• 基本算法：

  每一次從待排序的資料元素中選出最小（或最大）的一個元素，存放在序列的起始位置，直到全部待排序的資料元素排完。

實作：

//選擇排序
	public static void selectionSort(int data[])
	{
		for(int i=0;i<data.length;i++)
			{
				for(int j=i+1;j<data.length;j++)
				{
					if(data[j]<data[i])
					{
						int t = data[j];
						data[j] = data[i];
						data[i] = t;
					}	
				}
			}
	}