1.交換排序—冒泡排序(BubbleSort)
基本思想:在要排序的一組數中,對目前還未排好序的範圍内的全部數,自上而下對相鄰的兩個數依次進行比較和調整,讓較大的數往下沉,較小的往上冒。即:每當兩相鄰的數比較後發現它們的排序與排序要求相反時,就将它們互換。
算法分析:如果有n個數,則要進行n-1趟比較。在第1趟比較中要進行n-1次相鄰元素的兩兩比較,在第j趟比較中要進行n-j次兩兩比較。比較的順序從前往後,經過一趟比較後,将最值沉底(換到最後一個元素位置),最大值沉底為升序,最小值沉底為降序。
void bubbleSort(int a[], int n){
for(int i=0;i< n-1;++i){
for(int j=0;j < n-i-1; j++){
if(a[j] > a[j+1]){
int temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}
}
冒泡排序算法的改進:
對冒泡排序常見的改進方法是加入一标志性變量exchange,用于标志某一趟排序過程中是否有資料交換,如果進行某一趟排序時并沒有進行資料交換,則說明資料已經按要求排列好,可立即結束排序,避免不必要的比較過程。本文再提供以下兩種改進算法:
1. 設定一标志性變量pos,用于記錄每趟排序中最後一次進行交換的位置。由于pos位置之後的記錄均已交換到位,故在進行下一趟排序時隻要掃描到pos位置即可。
改進後算法如下:
void Bubble_1 ( int r[], int n) {
int i= n -1; //初始時,最後位置保持不變
while ( i> 0) {
int pos= 0; //每趟開始時,無記錄交換
for (int j= 0; j< i; j++)
if (r[j]> r[j+1]) {
pos= j; //記錄交換的位置
int temp = r[j];
r[j] = r[j+1];
r[j+1] = temp;
}
i= pos; //為下一趟排序作準備
}
}
算法分析:定義n-1次循環,每個數字比較n-j次,比較前一個數和後一個數的大小。然後交換順序。
2.傳統冒泡排序中每一趟排序操作隻能找到一個最大值或最小值,我們考慮利用在每趟排序中進行正向和反向兩遍冒泡的方法一次可以得到兩個最終值(最大者和最小者), 進而使排序趟數幾乎減少了一半。
改進後的算法實作為:
void Bubble_2 ( int r[], int n){
int low = 0;
int high= n -1; //設定變量的初始值
int tmp,j;
while (low < high) {
for (j= low; j< high; j++) //正向冒泡,找到最大者
if (r[j]> r[j+1]) {
tmp = r[j];
r[j] = r[j+1];
r[j+1] = tmp;
}
high--; //修改high值, 前移一位
for ( j=high; j>low; j++) //反向冒泡,找到最小者
if (r[j]<r[j-1]) {
tmp = r[j];
r[j] = r[j-1];
r[j-1] = tmp;
}
low++; //修改low值,後移一位
}
}
選擇排序—簡單選擇排序(Simple Selection Sort)
基本思想:在要排序的一組數中,選出最小(或者最大)的一個數與第1個位置的數交換;然後在剩下的數當中再找最小(或者最大)的與第2個位置的數交換,依次類推,直到第n-1個元素(倒數第二個數)和第n個元素(最後一個數)比較為止。
簡單選擇排序的示例:
操作方法:在要排序的一組數中,選出最小的一個數與第一個位置的數交換; 然後在剩下的數當中再找最小的與第二個位置的數交換,如此循環到倒數第二個數和最後一個數比較為止。
第i趟,則從第i 個記錄開始的n-i+1個記錄中選出關鍵碼最小的記錄與第i 個記錄交換,直到整個序列按關鍵碼有序。
算法分析:每趟選出一個最值和無序序列的第一個數交換,n個數共選n-1趟。第i趟假設i為最值下标,然後将最值和i+1至最後一個數比較,找出最值的下标,若最值下标不為初設值,則将最值元素和下标為i的元素交換.
算法實作:
void select_sort(int *x, int n) {
int i, j, min, t;
for (i=0; i<n-1; i++) {
min = i;
for (j=i+1; j<n; j++) {
if (*(x+j) < *(x+min)) {
min = j;
}
}
if (min != i) {
t = *(x+i);
*(x+i) = *(x+min);
*(x+min) = t;
}
}
}
(2)核心代碼:
for(i=0;i<n-1;i++) {
k=i;
for(j=i+1;j<n;j++)
if( a[k] < a[j])
k=j;
if( k != i) {
t = a[k];
a[k] = a[i];
a[i] = t;
}
}
算法特點:每趟是選出一個最值确定其在結果序列中的位置,确定元素的位置是從前往後,而每趟最多進行一次交換,其餘元素的相對位置不變。可進行降序排序或升序排序。
算法分析:定義外部n-1次循環,假設第一個為最值,放在參數中,在從下一個數以後找最值若後面有比前面假設的最值更大的就放在k中,然後在對k進行分析。若k部位最初的i值。也就是假設的i不是最值,那麼就交換最值和目前序列的第一個數。。。。