天天看點
傳回

八種常見的排序算法

1. 算法複雜度計算

2.1 首先看時間複雜度：

想要了解時間複雜度，就需要先了解時間頻度。一個算法花費的時間與算法中語句的執行次數成正比例，哪個算法中語句執行次數多，它花費時間就多。一個算法中的語句執行次數稱為語句頻度或時間頻度。記為T(n)。

接下來就引入了時間複雜度的概念。看一下比較官方的定義吧：一般情況下，算法中基本操作重複執行的次數是問題規模n的某個函數，用T(n)表示，若有某個輔助函數f(n),使得當n趨近于無窮大時，T(n)/f(n)的極限值為不等于零的常數，則稱f(n)是T(n)的同數量級函數。記作T(n)=O(f(n)),稱O(f(n)) 為算法的漸進時間複雜度，簡稱時間複雜度。是不是比較難以了解，說白了時間複雜度就是描述時間的規模，比如說時間頻度是T(n),時間複雜度就是O(n)。時間頻度是T(n+n)的時候,時間複雜度還是O(n)。也就是他的時間規模就是n這個層次了。

常見的算法的時間 複雜度之間的關系為：

O(1)<O(logn)<O(n)<O(nlog

n)<O(n^2 )<O(2^ n)<O(n!)<O(n^n)

為什麼時間複雜度用logn來描述，而不用log2n來描述？

假如有logaB（a為底數），由換底公式可得：

八種常見的排序算法

logcA（c為底數）為常數，由O的運算規則"O(C×f(N))=O(f(N))，其中C是一個正的常數"得O（logaB）=O（logcB）可知算法的時間複雜度與不同底數隻有常數的關系，均可以省略自然可以用logN代替。

2.2 空間複雜度

空間複雜度就比較容易了解了，空間複雜度是對一個算法在運作過程中臨時占用存儲空間大小的一個量度，同樣反映的是一個空間規模，我們用 S(n) 來定義。

空間複雜度比較常用的有：O(1)、O(n)、O(n²)

2.常見排序算法的複雜度

八種常見的排序算法

什麼是穩定排序和不穩定排序？

通俗地講就是能保證排序前2個相等的數其在序列的前後位置順序和排序後它們兩個的前後位置順序相同，則稱之為穩定排序。也就是排序前後兩個相等元素的相對位置不發生改變。比如A[i]=A[j],排序前i在j前面，排序後i還是在j之前。如果排序算法穩定，對基于比較的排序算法而言，元素交換的次數可能會少一些。

哪些是穩定排序和不穩定排序？

通常前後相鄰兩兩元素比較的排序是穩定的。

穩定的排序：冒泡排序、插入排序、歸并排序、基數排序

不穩定的排序：選擇排序、快速排序、希爾排序、堆排序

3. 冒泡排序

3.1 算法原理

S1：從待排序序列的起始位置開始，從前往後依次比較各個位置和其後一位置的大小并執行S2。

S2：如果目前位置的值大于其後一位置的值，就把他倆的值交換（完成一次全序列比較後，序列最後位置的值即此序列最大值，是以其不需要再參與冒泡）。

S3：将序列的最後位置從待排序序列中移除。若移除後的待排序序列不為空則繼續執行S1，否則冒泡結束。

3.2 算法實作 

public void sort(int[] nums) {
  for (int i = 0; i < nums.length; i++) {
   for (int j = 0; j < nums.length-1-i; j++) {
	    if(nums[j] > nums[j+1]) {
	     int temp = nums[j];
	     nums[j] = nums[j+1];
	     nums[j+1] = temp;
	    }
   }
  }
 }

3.3 算法優化

若某一趟排序中未進行一次交換，則排序結束。因為在一趟排序中沒有交換的話，說明前一個數一直小于後一個數。

public void sort(int[] nums) {
  for (int i = 0; i < nums.length; i++) {
   boolean flag = false;
   for (int j = 0; j < nums.length-1-i; j++) {
    if(nums[j] > nums[j+1]) {
     int temp = nums[j];
     nums[j] = nums[j+1];
     nums[j+1] = temp;
     flag = true;
    }
   }
   if(flag==false)
    break;
  }
 }

4.快速排序

4.1 算法原理

快速排序是對冒泡排序的一種改進。

基本思想是：通過一趟排序将要排序的資料分割成獨立的兩部分，其中一部分的所有資料都比另外一部分的所有資料都要小，然後再按此方法對這兩部分資料分别進行快速排序，整個排序過程可以遞歸進行，以此實作整個資料變成有序序列。

算法步驟：

  1. 假設我們對數組{7, 1, 3, 5, 13, 9, 3, 6,11}進行快速排序。
  2. 首先在這個序列中找一個數作為基準數，為了友善可以取第一個數。
  3. 周遊數組，将小于基準數的放置于基準數左邊，大于基準數的放置于基準數右邊。
  4. 此時得到類似于這種排序的數組{3, 1, 3, 5, 6, 7, 9, 13, 11}。
  5. 在初始狀态下7是第一個位置，現在需要把7挪到中間的某個位置k，也即k位置是兩邊數的分界點。
  6. 那如何做到把小于和大于基準數7的值分别放置于兩邊呢，我們采用雙指針法，從數組的兩端分别進行比對。
  7. 先從最右位置往左開始找直到找到一個小于基準數的值，記錄下該值的位置（記作 i）。

  8. 再從最左位置往右找直到找到一個大于基準數的值，記錄下該值的位置（記作 j）。

    注意：一定要先從右往左找到小于基準值target的值，再從左往右找到小于target的值，因為如果先從左往右找到大于target的值，此時nums[i]>target的，再早小于的target的時候，如果i==j，那麼就會将nums[i]和target交換位置，此時target的左邊就會出現一個大于它的數，不符合快速排序的要求。

  9. 如果位置i<j，則交換i和j兩個位置上的值，然後繼續從(j-1)的位置往前和(i+1)的位置往後重複上面比對基準數然後交換的步驟。
  10. 如果執行到i==j，表示本次比對已經結束，将最後i的位置的值與基準數做交換，此時基準數就找到了臨界點的位置k，位置k兩邊的數組都比目前位置k上的基準值或都更小或都更大。
  11. 上一次的基準值7已經把數組分為了兩半，基準值7算是已歸位（找到排序後的位置）。
  12. 通過相同的排序思想，分别對7兩邊的數組進行快速排序，左邊對[left, k-1]子數組排序，右邊則是[k+1, right]子數組排序。
  13. 利用遞歸算法，對分治後的子數組進行排序。

快速排序之是以比較快，是因為相比冒泡排序，每次的交換都是跳躍式的，每次設定一個基準值，将小于基準值的都交換到左邊，大于基準值的都交換到右邊，這樣不會像冒泡一樣每次都隻交換相鄰的兩個數，是以比較和交換的此數都變少了，速度自然更高。

4.2 算法實作 

public void sort(int[] nums,int left,int right) {
		if(left>=right)
			return ;
		int target = nums[left];
		int i = left;
		int j = right;
		while(i < j) {
			//從右往左找到小于target的值
			while(nums[j] >= target && i<j) {
				j--;
			}
			//從左往右找到大于target的值
			while(nums[i] <= target && i<j) {
				i++;
			}

			if(i < j){
					int temp = nums[i];
					nums[i] = nums[j];
					nums[j] = temp;
					i++;
					j--;
			}
		}
		//将基準數歸位
		nums[left] = nums[i];
		nums[i] = target;
		sort(nums,left,i-1);
		sort(nums,i+1,right);
	}
}

為什麼說快速排序是對冒泡排序的一種改進？

因為冒泡排序是将大的數往右移動，小的數往做移動。而快速排序有兩個序列，分别存儲大的數和小的數，大于target的數放在大數序列，小于target的數放在小數序列。

4.3 算法改進

改進思路：

（1）分而治之時候，分到了最後，數組已經很小，這時候采用插入排序代替快速排序。

（2）基準值的選取，我們随機取出來3個數，取中間大小的為基準值。

（3）取三個變量切分數組，将數組分為大于，等于，小于基準元素三部分，這樣在遞歸時就可以剔除相等的元素，減小比較的次數

private static void sort(Comparable[] a,int low,int height){  
     //改進處1：由插入排序替換
     if(height <= low + M){//M取5-15
           InsertSort.sort(a,lo,hi);
           return;  
    } 
    //改進處3：三向切分
    int lt=low,i=low+1,gt=height;  //三個變量，
    //改進處2：基準元素的選取
    int i=medianOf3(a,low,low+(height-low)/2, height);

    while(i<=gt){
        int cmp = a[i].compareTo(a[low]);
        if(cmp<0) 
            exch(a,lt++,i++);  
        else if(cmp>0)
            exch(a,i,gt--);   
        else 
            i++;    
        }
    sort(a,low,lt-1); 
    sort(a,lt+1,height);
}

這裡面有倆函數，medianOf3和exch。medianOf3函數是找到三個數的中間值，exch是交換兩個數的位置

5.直接插入排序

5.1 算法原理

插入排序的基本方法是：每步将一個待排序序列按資料大小插到前面已經排序的序列中的适當位置，直到全部資料插入完畢為止。

（1) 将這個序列的第一個元素視為一個有序序列；

（2）預設從第二個資料開始比較。

（3）如果第二個資料比第一個小，則交換。然後在用第三個資料比較，如果比前面小，則插入（狡猾）。否則，退出循環

（4）說明：預設将第一資料看成有序清單，後面無序的清單循環每一個資料，如果比前面的資料小則插入（交換），否則退出。

5.2 算法實作 

public void sort(int[] nums) {
		for (int i = 1; i < nums.length; i++) {
			for (int j = i; j > 0; j--) {
				if(nums[j] >= nums[j-1])
					break;
				else {
					int temp = nums[j];
					nums[j] = nums[j-1];
					nums[j-1] = temp;
				}
			}
		}
	}

5.3 算法改進

每次找插入位置的時候我們都要從頭到尾一個一個比較。當資料量大的時候我們肯定不允許。于是我們換一種想法。使用二分法查找的思想，使用二分法查找應該插入的位置。

//使用二分查找進行插入排序
	public void sort(int[] nums) {
		for (int i = 1; i < nums.length; i++) {
			//從已經排好序的數組0---i-1中找到nums[i]插入的位置
			int temp = nums[i];
			int left = 0;
			int right = i-1;
			int mid = (left+right)/2;
			//找到待插入的位置right+1
			while(left <= right) {
				if(nums[i] <= nums[mid]) {
					right = mid-1;
				}
				else {
					left = mid+1;
				}
				mid = (left+right)/2;
			}
			//将待插入位置後面所有元素往後移動一位
			for (int j = i; j > right+1; j--) {
				nums[j] = nums[j-1];
			}
			nums[right+1] = temp;
			System.out.println(Arrays.toString(nums));
		}
		
	}

6. 希爾排序

希爾排序是插入排序的變種版。希爾排序是一種插入排序算法，又稱作縮小增量排序，是一種分組插入排序的方法。

6.1 算法原理

（1）将數組nums分成若幹個子數組，子數組元素之間的步長為i，i的初始值為nums.length/2,i最小值為1，并且每次循環後i變成i/2。

（2）對每個子數組進行插入排序，首先控制子數組開始的位置j，j < nums.length-i

（3）對每個子數組元素從第二個元素開始進行判斷，如果大于前一個元素，直接退出該層循環，如果小于前一個元素則交換

6.2 算法實作 

public static void sort(int[] nums) {
		int len = nums.length;
		//希爾排序的步長,最長為len/2,最短為1
		for (int i = len/2; i > 0; i/=2) {
			//插入排序i個子數組的開始位置j
			for (int j = 0; j <= i; j++) {
				//每個子數組插入排序交換元素
				for (int k = j+i; k < nums.length;) {
					if(nums[k] < nums[k-i]) {
						int temp = nums[k-i];
						nums[k-i] = nums[k];
						nums[k] = temp;
					}
					//找到了插入位置，退出循環
					else {
						break;
					}
					k = j+i;
				}
			}
		}
	}

6.3 算法改進

（1）對增量序列優化：使用更加複雜的方式。

（2）對每一趟的插入排序進行優化：在内循環中，總是将較大的元素向右移動。

7. 直接選擇排序

7.1 算法原理

直接選擇排序是一種簡單的排序方法，它的基本思想是：

第一次從R[0]~R[n-1]中選取最小值，與R[0]交換，

第二次從R[1]~R[n-1]中選取最小值，與R[1]交換，

….，

第i次從R[i-1]~R[n-1]中選取最小值，與R[i-1]交換，

……，

第n-1次從R[n-2]~R[n-1]中選取最小值，與R[n-2]交換，

共通過n-1次，得到一個從小到大排列的有序序列。

7.2 算法實作 

public void sort(int[] nums) {
		for (int i = 0; i < nums.length-1; i++) {
			for (int j = i+1; j < nums.length; j++) {
				if(nums[i] > nums[j]) {
					int temp = nums[i];
					nums[i] = nums[j];
					nums[j] = temp;
				}
			}
		}
	}

7.3 算法優化

之前的算法中，每跑一趟，隻能選出來一個最大的元素或者是一個最小的元素，但是歸根結底是一個元素。這樣的話有N個元素，就要跑N-1趟。現在我們換一種思路。

每跑一趟不僅僅記錄最大的元素還可以記錄最小的元素，這不是一舉兩得嘛。這時候隻需要跑N/2趟即可。省時省力。

//選擇排序改進版
       public static void selectSort(int[] arr){
           int minPoint;  //存儲最小元素的小标
           int maxPoint;  //存儲最大元素的小标
           int len = arr.length;
           int temp;
           //隻需要跑N/2趟即可
           for(int i=0;i<len/2;i++){   
              minPoint= i;
              maxPoint= i;
              for(int j=i+1;j<=len-1-i;j++){ 
                  //每一趟的最小值
                  if(arr[j]<arr[minPoint]){  
                     minPoint= j;
                     continue;
                  }
                  //每一趟的最小值
                  else if(arr[j]>arr[maxPoint]){ 
                     maxPoint= j;
                  }
              }
             //将最小值與前面的值交換
              if(minPoint!=i){  
                  temp= arr[i];
                  arr[i]= arr[minPoint];
                  arr[minPoint]= temp;
                  if(maxPoint== i){
                     maxPoint= minPoint;
                  }

              }
             //将最大值與後面的值交換
              if(maxPoint!=len-1-i){  
                  temp= arr[len-1-i];
                  arr[len-1-i]= arr[maxPoint];
                  arr[maxPoint]= temp;
              }         
           }
       }

8. 堆排序

參考自堆排序算法（圖解詳細流程）

8.1 算法原理

堆排序（Heapsort）是指利用堆這種資料結構（後面的【圖解資料結構】内容會講解分析）所設計的一種排序算法。堆積是一個近似完全二叉樹的結構，并同時滿足堆積的性質：即子結點的鍵值或索引總是小于（或者大于）它的父節點。堆排序可以說是一種利用堆的概念來排序的選擇排序。分為兩種方法：

  • 大頂堆：每個節點的值都大于或等于其子節點的值，在堆排序算法中用于升序排列；
  • 小頂堆：每個節點的值都小于或等于其子節點的值，在堆排序算法中用于降序排列；

堆排序的平均時間複雜度為 Ο(nlogn)。

1.父結點索引：(i-1)/2（這裡計算機中的除以2，省略掉小數）

2.左孩子索引：2*i+1

3.右孩子索引：2*i+2

堆的定義性質：

大根堆：arr(i)>arr(2i+1) && arr(i)>arr(2i+2)

小根堆：arr(i)<arr(2i+1) && arr(i)<arr(2i+2)

8.2 算法步驟

  1. 首先将待排序的數組構造成一個大根堆，此時，整個數組的最大值就是堆結構的頂端
  2. 将頂端的數與末尾的數交換，此時，末尾的數為最大值，剩餘待排序數組個數為n-1
  3. 将剩餘的n-1個數再構造成大根堆，再将頂端數與n-1位置的數交換，如此反複執行，便能得到有序數組

8.3 算法實作 

public static void sort(int[] nums){
    	//1.建構大頂堆
    	heapInsert(nums);
    	int size = nums.length;
    	while(size > 1) {
    		//将堆頂元素放到末尾
    		swap(nums,0,size-1);
    		System.out.println(Arrays.toString(nums));
    		size--;
    		//将剩餘元素重新構造大頂堆
    		heapify(nums,0,size);
    	}
    	
    }
    
    //構造大頂堆，通過新插入的數上升
    public static  void heapInsert(int[] nums) {
    	for (int i = 0; i < nums.length; i++) {
			//目前插入的索引
    		int currentIndex = i;
    		//父節點
    		int fatherIndex = (currentIndex-1)/2;
    		//如果目前值大于父節點值則交換，并且将索引指向父節點
    		while(nums[currentIndex] > nums[fatherIndex]) {
    			swap(nums, currentIndex, fatherIndex);
    			currentIndex = fatherIndex;
    			fatherIndex = (currentIndex-1)/2;
    			
    		}
		}
    }
    
    //剩餘的樹構造大頂堆
    public static void heapify(int[] nums,int index,int size) {
    	//左節點
    	int left = 2*index+1;
    	//右節點
    	int right = 2*index+2;
    	while(left < size) {
    		int maxIndex;
    		//選擇子節點較大的那一個
    		if(nums[left] < nums[right] && right < size)
    			maxIndex = right;
    		else
    			maxIndex = left;
    		if(nums[index] >= nums[maxIndex]) {
    			break;
    		}
    		else {
    			swap(nums, index, maxIndex);
    			index = maxIndex;
    			left = 2*index+1;
    	    	right = 2*index+2;
    		}
    	}
    }
    
    public static void swap(int[] nums,int i,int j) {
    	int temp = nums[i];
    	nums[i] = nums[j];
    	nums[j] = temp;
    }

9. 歸并排序

9.1 算法原理

歸并排序的算法我們通常用遞歸實作，先把待排序區間[s,t]以中點二分，接着把左邊子區間排序，再把右邊子區間排序，最後把左區間和右區間用一次歸并操作合并成有序的區間[s,t]。

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

S2: 設定兩個指針，最初位置分别為兩個已經排序序列的起始位置

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

S4: 重複S3，直到某一指針超出序列尾

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

9.2 算法實作 

public void mergeSort(int[] nums,int low,int high) {
		int mid = (low+high)/2;
		if(low<high) {
			mergeSort(nums, low, mid);
			mergeSort(nums, mid+1, high);
			merge(nums, low, mid, high);
		}
	}
	public void merge(int[] nums,int low,int mid,int high) {
		int[] tempArr = new int[high-low+1];
		int i = low;
		int j = mid+1;
		int index = 0;
		while(i <= mid && j <= high) {
			if(nums[i] < nums[j]) {
				tempArr[index++] = nums[i++];
			}
			else {
				tempArr[index++] = nums[j++];
			}
		}
		while(i<=mid) {
			tempArr[index++] = nums[i++];
		}
		while(j<=high) {
			tempArr[index++] = nums[j++];
		}
		for (int k = low; k <= high; k++) {
			nums[k] = tempArr[k-low];
		}
	}

9.3 算法改進

（1）如果子數組較小，改用插入排序；

（2） 兩個子數組若已經有序，則直接複制進數組

（3） 通過交換參數來避免每次都要複制到輔助數組。

private static void sort(Comparable[] a, Comparable[] aux,int low, int height){
        int mid = low + (height -low) / 2;  
        //改進1：若子序列比較短，則直接使用插入排序
        if(height <= low + 7 - 1){  
            insertionSort(a, lo, hi);
            return;
        }       
        sort(aux,a,low,mid);     
        sort(aux,a,mid+1,height);  
        //less函數比較a[mid+1]和a[mid]的大小
        //改進2：如果數組已經有序則直接複制，不再merge
        if(!less(a[mid+1],a[mid])){ 
            System.arraycopy(aux, low, a, low, height-low+1);
            return;
        }
        merge(a,aux,low,mid,height); 
    }
	private void merge(Comparable[] a,Comparable[] aux, int lo, int mid, int hi){
	    //左半部分
	    for(int k = low; k <= mid; k++)
	        aux[k] = a[k];
	    //右半部分
	    for(int k = mid+1; k <= height; k++)
	        aux[k] = a[height+mid+1-k];
	    int i = low, j = height; 
	    //整個序列
	    for(int k=low;k<=height; k++ ){
	        if(less(aux[j],aux[i]))
	            a[k] = aux[j--];
	        else 
	            a[k] = aux[i++]; 
	    }           
	}

10.基數排序

資料結構分析
上一篇: js實作八種排序算法
下一篇: [算法學習]常用排序算法實作

繼續閱讀