（二）排序演算法總結（內排序）

1. 基本概念

1.1:什么是排序：

排序是計算機程式設計中的一項重要操作，其功能是指一個資料元素集合或序列重新排列成一個按資料元素某個資料項值有序的序列，

1.2 :排序的分類：（內排序和外排序）

1：內排序：指的是待排序列完全存放在記憶體中所進行的排序，其又可分為五大類排序：選擇排序、插入排序、交換排序、歸并排序和分配排序，
2：外排序：指的是排序程序中還需要訪問外部存盤器的排序，

2.（簡單）選擇排序

2.1：基本原理：

將待排序元素分為已排序（初始為空）和未排序兩組，依次將未排序元素中值最小的元素放入到已排序的組別中，

2.2：排序基本程序：

1. 在一組元素R[i]到R[n]中選擇具有最小關鍵碼的元素
2. 若它不是這組元素中的第一個元素，則將它與這組元素中的第一個元素交換位置，
3. 除去具有最小關鍵字的元素，在剩下的元素中重復第1.2步驟，直到剩余元素只有一個為止，

2.3：示例：

2.4：動態演示：

2.5：演算法：

   for(int i = 0; i < arr.length - 1; i++) {//進行n-1趟排序
            int k = i;
            for(int j = k + 1; j < arr.length; j++){// 選最小的記錄
                if(arr[j] < arr[k]){ 
                    k = j; //記下目前找到的最小值所在的位置
                }
            }
            //元素交換
            if(i != k){
                int temp = arr[i];
                arr[i] = arr[k];
                arr[k] = temp;
            }    
        }

2.6：演算法分析：

1. 無論初始狀態如何，在第i趟排序中選擇最小關鍵碼的元素需要進行n-i次比較，則時間復雜度為O(n^2)
2. 最好的情況：序列為正序時，移動次數為0，
3. 最壞的情況：序列為反序時，每次排序都要執行交換操作，總移動次數為3（n-1）（最大值）
4. 其排序是不穩定的

3.（直接）插入排序

3.1：基本原理：

每次將一個待排的元素，按其關鍵字大小插入到前面已經排號序的子檔案的合適位置，直到全部記錄插入完成為止，

3.2：排序基本程序：

將n個待排序的元素看成一個有序表和一個無序表，開始時有序表中只包含有一個元素，無序表中有n-1個元素，將它的排序碼依次跟有序表元素的排序碼相比較，將它插入到有序表的適當位置，使之成為新的有序表，

3.3：示例：

3.4：動態演示：

3.5：演算法：

 public static void D-insertSort(int [] array){
        for(int i=0;i<array.length;i++){
            //有序[0,i)
            //無序[i,array.length)
            int j=i-1;
            int key=array[i];
            for(;j>=0 && key<array[j];j--){
                array[j+1]=array[j];//元素后移
            }
            array[j+1]=key;//將key中的第i個元素插入到有序表中
        }

3.6：演算法分析：

1. 空間角度：它只需要一個元素的輔助空間來用于元素的位置交換
2. 時間角度：最外層回圈需要n-1次插入操作，每次插入最少比較一次（正序），移動0次；最多比較i次，移動i+1次（逆序），則其時間復雜度為：O(n^2)
3. 其是穩定的，

4.堆排序

4.1：基本原理：

4.2：排序基本程序：

1. 根據初始輸入資料形成初始堆
2. 通過一系列的元素交換和重新調整堆進行排序

4.3：示例：（以大根堆為例）

4.4：動態演示：

4.5：演算法：

	/**
	 * 
	     * @Title: buildHeap
	     * @Description: TODO(初始堆結構（完全二叉樹的順序結構）)
	     * @param @param arr
	     * @param @return 引數
	     * @return int[] 回傳型別
	     * @throws
	 */
	    private int[] buildHeap(int[] arr){
	        //從最后一個節點array.length-1的父節點（array.length-1-1）/2開始，直到根節點0，反復調整堆
	        for(int i=(arr.length-2)/2;i>=0;i--){
	            setHeap(arr, i,arr.length);
	        }
	        return arr;
	    }
	    /**
	     * 
	         * @Title: setHeap
	         * @Description: TODO(調整堆結構)
	         * @param @param arr
	         * @param @param t
	         * @param @param length 引數
	         * @return void 回傳型別
	         * @throws
	     */
	    private void setHeap(int[] arr,int t,int length){
	        int temp = arr[t];
	        for(int i=2*t+1; i<length-1; i=2*i+1){    //i為初始化為節點k的左孩子，沿節點較大的子節點向下調整
	            if(i<length && arr[i]<arr[i+1]){  //取節點較大的子節點的下標
	                i++;   //如果節點的右孩子>左孩子，則取右孩子節點的下標
	            }
	            if(temp>=arr[i]){  //根節點 >=左右孩子中關鍵字較大者，調整結束
	                break;
	            }else{   //根節點 <左右孩子中關鍵字較大者
	                arr[t] = arr[i];  //將左右子結點中較大值array[i]調整到雙親節點上
	                t = i; //【關鍵】修改k值，以便繼續向下調整
	            }
	        }
	        arr[t] = temp;  //被調整的結點的值放人最終位置
	    }
		/**
		 * 
		     * @Title: heapSort
		     * @Description: TODO(進行堆排序)
		     * @param @param arr
		     * @param @return 引數
		     * @return int[] 回傳型別
		     * @throws
		 */
	    public int[] heapSort(int[] arr){
	        arr = buildHeap(arr); //初始建堆，array[0]為第一趟值最大的元素
	        for(int i=arr.length-1;i>1;i--){
	            int temp = arr[0];  //將堆頂元素和堆低元素交換，即得到當前最大元素正確的排序位置
	            arr[0] = arr[i];
	            arr[i] = temp;
	            setHeap(arr, 0,i);  //整理，將剩余的元素整理成堆
	        }
	        return arr;
	    }
	}

4.6：演算法分析：

1. 在整個堆排序中，需要進行Ln/2]+n-1次篩選運算，每次運算進行雙親和孩子或兄弟結點的排序碼的比較和移動次數都不會超過完全二叉樹的深度Llog2n]+1,所以，每次運算的時間復雜度為：
   則整個堆排序程序時間復雜度為：：
2. 堆排序的時間復雜度與序列的初始狀態無關，但是比較次數跟初始狀態有關，
3. 其空間復雜度為O(1),占用的輔助空間為1
4. 其是不穩定的

5.歸并排序

5.1：基本原理：

將兩個有序表合并為一張有序表

5.2：排序基本程序：

順序比較兩個已經排序好的表的相應元素，小的移入到另一個表，重復上述步驟直到其中任意一個表都移動到另外一個表為止，

5.3：示例：

5.4：動態演示：

5.5：演算法：

/**
	 * 
	     * @Title: mergeSort
	     * @Description: TODO(歸并排序)
	     * @param @param arr 待排陣列
	     * @param @param left 左邊
	     * @param @param right 右邊
	     * @return void 回傳型別
	     * @throws
	 */
	public static void mergeSort(int[] arr, int left, int right) {
		if(null == arr) {
			return;
		}
		
		if(left < right) {
			//找中間位置進行劃分
			int mid = (left+right)/2;
			//對左子序列進行遞回歸并排序
			mergeSort(arr, left, mid);
			//對右子序列進行遞回歸并排序
			mergeSort(arr, mid+1, right);
			//進行歸并
			merge(arr, left, mid, right);
		}
	}

/**
 * 
     * @Title: merge
     * @Description: TODO(進行歸并操作)
     * @param @param arr
     * @param @param left 左邊
     * @param @param mid 中間
     * @param @param right 右邊
     * @return void 回傳型別
     * @throws
 */
	private static void merge(int[] arr, int left, int mid, int right) {
		int[] tempArr = new int[arr.length];//臨時陣列
		int leftStart = left;//左邊開始下標
		int rightStart = mid+1;//右邊開始下標
		int tempIndex = left;
		
		while(leftStart <= mid && rightStart <= right) {
			if(arr[leftStart] < arr[rightStart]) {
				tempArr[tempIndex++] = arr[leftStart++];
			} else {
				tempArr[tempIndex++] = arr[rightStart++];
			}	
		}
		
		while(leftStart <= mid) {
			tempArr[tempIndex++] = arr[leftStart++];
		}
		
		while(rightStart <= right) {
			tempArr[tempIndex++] = arr[rightStart++];
		}
		
		while(left <= right) {
			arr[left] = tempArr[left++];
		}

	}

5.6：演算法分析：

1. 
2. 利用二路歸并排序時，需要利用和待排序陣列相同的輔助陣列作為臨時單元，則該排序方法的空間復雜度為O(n)
3. 其是穩定的

6.冒泡排序

6.1：基本原理：

通過對待排序序列從前往后，依次比較相鄰元素的排序碼，若發現逆序則交換，使排序碼大的元素逐漸從前部移到尾部

6.2：排序基本程序：

6.3：動態演示：

6.4：演算法：

	/**
	 * 
	     * @Title: BubbleSort
	     * @Description: TODO(冒泡排序)
	     * @param @param arr 待排陣列
	     * @return void 回傳型別
	     * @throws
	 */
	 public static void BubbleSort(int[] arr) {
	        int temp;//定義一個臨時變數
	        for(int i=0;i<arr.length-1;i++){//冒泡趟數
	            for(int j=0;j<arr.length-i-1;j++){
	                if(arr[j+1]<arr[j]){
	                    temp = arr[j];
	                    arr[j] = arr[j+1];
	                    arr[j+1] = temp;
	                }
	            }
	        }
	 }

6.5：演算法分析：

1. 若是正序，則只需要一趟排序，比較次數為（n-1）次，移動元素次數為0
2. 若是逆序，則需進行n-1趟排序，比較次數為（n^2-n）/2，
   移動次數為：3n^2-n）/2
3. 其時間復雜度為O(n^2)
4. 其是穩定的，只進行元素間的順序移動

7.快速排序

7.1：基本原理：

任取待排序序列中的某個元素作為標準，通過一次劃分，將待排元素分為左右兩個子序列，左子序列元素的排序碼都小于基準元素的排序碼，右子序列元素的排序碼都大于或等于基準元素的排序碼，接著分別對兩個子序列繼續進行劃分，直到每一個序列只有一個元素為止，

7.2：排序基本程序：

7.3：示例：

7.4：動態演示：

7.5：演算法：

/**
		 * 
		     * @Title: quickSort
		     * @Description: TODO(快速排序)
		     * @param @param arr 待排陣列
		     * @param @param left 左下標
		     * @param @param right 右下標
		     * @return void 回傳型別
		     * @throws
		 */
	    public void quickSort(int[] arr,int left,int right){
	        if (left<right){
	            int temp=arr[left];//基準位
	            while (left<right){
	            	//右邊，依次向左遞減
	                while (left<right && arr[right]>temp){
	                    right--;
	                }
	                if (left<right){
	                    arr[left++]=arr[right];
	                }
	              //左邊，依次向右遞增
	                while (left<right && arr[left]<=temp){
	                    left++;
	                }
	                if (left<right){//元素交換
	                    arr[right--]=arr[left];
	                }
	            }
	            arr[left]=temp;
	            quickSort(arr,left,temp-1);//遞回呼叫左邊部分
	            quickSort(arr,temp+1,right);//遞回呼叫右邊部分
	        }
	    }

7.6：演算法分析：

8.希爾排序

8.1：基本原理：

先將整個待排元素序列分割為若干個子序列分別繼續直接插入排序，待整個序列中的元素基本有序時再對整體元素進行一次直接插入排序，

8.2：示例：

8.3：動態演示：

8.4：演算法：

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

8.5：演算法分析：

9.總結：