今天繼續對排序做個整理吧 三個簡單排序—冒泡，選擇，直接插入
首先是冒泡排序(Bubble Sort )：
比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最后一對。這步做完后，最后的元素會是最大的數。針對所有的元素重復以上的步驟，除了最后一個。持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較
時間復雜度 O(n^2) 最優時間復雜度 O(n) 平均時間復雜度 O(n^2)
C語言實現：
//冒泡排序初級版void BubbleSort0(int *arr, int len){ int i; int j; for(i = 0; i < len; i++) { for(j = i + 1; j < len; j++) { if(arr[i] > arr[j]) { Swap(arr,i, j); } } }}//正宗冒泡排序void BubbleSort(int *arr, int len){ int i; int j; for(i = 0; i < len; i++) { for(j = len -1; j >= i; j--) //j從后往前，將小的值交換到i的位置 { if(arr[i] > arr[j]) { Swap(arr, i, j); } } } }//優化冒泡排序_對于已經有序的序列不再進行循環void BubbleSort1(int *arr, int len){ int i; int j; bool flag = true; //增加一個flag作為標記 for(i = 0; i < len && flag; i++) //若flag = true 則退出循環 { flag = false; //初始化為false for(j = len -1; j >= i; j--) { if(arr[i] > arr[j]) { Swap(arr, i, j); flag = true; //如果有數據交換,則flag = ture } } } }選擇排序(Selection sort)：
首先在未排序序列中找到最?。ù螅┰?，存放到排序序列的起始位置，然后，再從剩余未排序元素中繼續尋找最?。ù螅┰?，然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。
時間復雜度 О(n2) 最優時間復雜度 О(n2) 平均時間復雜度 О(n2)
C語言實現如下：
void SelectSort(int *arr, int len){ int i; int j; int min; for(i = 0; i < len; i++) { min = i; //將當前下標作為最小值下標 for(j = i + 1; j < len; j++) { if(arr[i] > arr[j]) { min = j; //找到最小值，將最小值下標給min if(i != min) { Swap(arr, i, min); } } } }}直接插入排序(Insertion Sort)：
通過構建有序序列，對于未排序數據，在已排序序列中從后向前掃描，找到相應位置并插入。插入排序在實現上，通常采用in-place排序（即只需用到O(1)的額外空間的排序），因而在從后向前掃描過程中，需要反復把已排序元素逐步向后挪位，為最新元素提供插入空間。
時間復雜度 O(n^2) 最優時間復雜度 O(n) 平均時間復雜度 O(n^{2})
C語言實現如下：
void InsertSort(int *arr, int len){ int i; int j; int tmp; for (i = 1; i < len; i++) { tmp = arr[i]; j = i - 1; for (; j >= 0 && arr[j] > tmp; j--) arr[j + 1] = arr[j];//最后一次執行該語句后，跳出當前for循環前，會再一次執行j-- arr[j + 1] = tmp;//執行完上一個語句（即for語句）后，跳出的位置保存在j中，此時arr[j]的值是沒有經過移動的，不能替換，應該替換的是arr[j+1] }}二分插入排序(BinarySort)：
是插入排序的一種變形，由于用到了二分查找算法，所以叫做二分插入排序，這樣關鍵字的比較次數就會減少，數量級為O(nlog^2n)，但是元素移動次數還是O(n^2)，所以二分插入排序的時間復雜度是O(n^2)。int Binary_Search(int *arr, int len, int key){ int low = 0; int high = len; while (low <= high ) { int mid = (low + high ) / 2; if (arr[mid] > key) { high = mid - 1; } else low = mid + 1; } return low; }//將數組分為倆個區域 //有序區 0 -- （i-1） --> 初始有一個元素//無序區 i -- (len-1)void BinarySort(int *arr, int len){ for (int i = 1; i < len; i++) { int tmp = arr[i]; int index = Binary_Search(arr, i - 1, tmp); for (int j = i; j > index; j--) { arr[j] = arr[j - 1]; } arr[index] = tmp; }}參考：
二分法插入排序_百度百科 折半插入排序–倆種java實現方法 二分搜索算法-維基百科
新聞熱點
疑難解答
