在C++中，排序也是一個很重要的東西，下面就對常見的排序算法進(jìn)行一個總結(jié) 1.交換函數(shù)
void swap(int *a, int i, int j) //交換兩個數(shù) { if(i==j) return; int tmp = a[i]; a[i] = a[j]; a[j] = tmp; }（1）冒泡排序 依次比較相鄰的數(shù)據(jù)，將小數(shù)據(jù)放在前，大數(shù)據(jù)放在后；即第一趟先比較第1個和第2個數(shù)，大數(shù)在后，小數(shù)在前，再比較第2個數(shù)與第3個數(shù)，大數(shù)在后，小數(shù)在前，以此類推則將最大的數(shù)”滾動”到最后一個位置；第二趟則將次大的數(shù)滾動到倒數(shù)第二個位置……第n-1(n為無序數(shù)據(jù)的個數(shù))趟即能完成排序。 以下面5個無序的數(shù)據(jù)為例： 40 8 15 18 12 （文中僅細(xì)化了第一趟的比較過程） 第1趟: 8 15 18 12 40 第2趟: 8 15 12 18 40 第3趟: 8 12 15 18 40 第4趟: 8 12 15 18 40
void bubblesort(int *arr,int nsize) { //排序，從i開始排，總是在[i+1,nsize]去尋找比當(dāng)前元素小的，并且交換，使得當(dāng)前位置的值總是其后面最小的。 for (int i = 0; i < nsize; i++) for (int j = i + 1; j < nsize; j++) if (arr[i] > arr[j]) swap(arr, i,j); }（2）選擇排序 以升序?yàn)槔热缭谝粋€長度為N的無序數(shù)組中， 在第一趟遍歷N個數(shù)據(jù)，找出其中最小的數(shù)值與第一個元素交換， 第二趟遍歷剩下的N-1個數(shù)據(jù)，找出其中最小的數(shù)值與第二個元素交換…… 第N-1趟遍歷剩下的2個數(shù)據(jù)，找出其中最小的數(shù)值與第N-1個元素交換， 至此選擇排序完成。 以下面5個無序的數(shù)據(jù)為例： 56 12 80 91 20（文中僅細(xì)化了第一趟的選擇過程） 第1趟：12 56 80 91 20 第2趟：12 20 80 91 56 第3趟：12 20 56 91 80 第4趟：12 20 56 80 91
void selectsort(int *arr, int nsize) { for (int i = 0; i < nsize; i++) { //arr[i+1....nsize-1]中找到當(dāng)前最小值及其位置（準(zhǔn)備與當(dāng)前a[i]調(diào)換） int min = arr[i]; int minpos = i; for (int j = i + 1; j < nsize; j++) { if (arr[j] < min) { min = arr[j]; //當(dāng)前最小值 minpos = j;//記錄當(dāng)前最小值的位置 } } swap(arr, i, minpos);//交換最小值位置，a[0....i]已經(jīng)有序 } }（3）插入排序 像撲克摸牌一樣，插入即表示將一個新的數(shù)據(jù)插入到一個有序數(shù)組中，并繼續(xù)保持有序。例如有一個長度為N的無序數(shù)組，進(jìn)行N-1次的插入即能完成排序；第一次，數(shù)組第1個數(shù)認(rèn)為是有序的數(shù)組，將數(shù)組第二個元素插入僅有1個有序的數(shù)組中；第二次，數(shù)組前兩個元素組成有序的數(shù)組，將數(shù)組第三個元素插入由兩個元素構(gòu)成的有序數(shù)組中……第N-1次，數(shù)組前N-1個元素組成有序的數(shù)組，將數(shù)組的第N個元素插入由N-1個元素構(gòu)成的有序數(shù)組中，則完成了整個插入排序。 以下面5個無序的數(shù)據(jù)為例： 65 27 59 64 58 （文中僅細(xì)化了第四次插入過程） 第1次插入: 27 65 59 64 58 第2次插入: 27 59 65 64 58 第3次插入: 27 59 64 65 58 第4次插入: 27 58 59 64 65
void insertsort(int *arr, int nsize) { int i, j, key; for (i = 1; i<nsize; i++)//控制需要插入的元素 { key = arr[i]; //key為當(dāng)前要插入的元素，將其插入到有序段arr[0,i-1] j = i - 1; while (j >= 0 && arr[j] > key) //查找要插入的位置,循環(huán)結(jié)束時(shí)則找到插入位置j { arr[j+1] = arr[j]; //移動元素的位置.供要插入元素使用 j--; } arr[j+1] = key; //插入指定元素到指定位置 } }（4）快速排序 快速排序是C.R.A.Hoare于1962年提出的一種劃分交換排序。它采用了一種分治的策略，該方法的基本思想是： 1．先從數(shù)列末尾取出一個數(shù)作為基準(zhǔn)元。 2．分區(qū)過程，將比這個數(shù)大的數(shù)全放到它的右邊，小于或等于它的數(shù)全放到它的左邊。 3．再對左右區(qū)間重復(fù)第二步，直到各區(qū)間只有一個數(shù)。
//手動快速默寫快排：先劃界，再分治.... int quickPartion(int *arr, int low, int high) { int pos = rand() % (high - low + 1) + low; swap(arr, pos, high);//將末尾的元素隨機(jī)化,防止極端情況 int key = arr[high];//總是將末尾元素選為關(guān)鍵化界元 int i = low - 1;//總是記錄比key小的元素最前面的位置 for (int j = low; j <= high - 1; j++) { if (arr[j] <= key) swap(arr, ++i, j); } swap(arr, ++i, high); return i;//返回“中間位置” } void QuickSort(int *arr, int low, int high) { if (low < high) { int mid = quickPartion(arr, low, high); QuickSort(arr, low, mid - 1); QuickSort(arr, mid + 1, high); } }新聞熱點(diǎn)
疑難解答
圖片精選
