今天繼續對排序做個整理吧 三個簡單排序—冒泡,選擇,直接插入
首先是冒泡排序(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實現方法 二分搜索算法-維基百科
新聞熱點
疑難解答