一. 冒泡排序
我們常常在寫冒泡排序的時候會將待排序數(shù)列從第一個元素開始依次和后面的每一個元素進行比對和交換棚亩，但是這種做法并沒有體現(xiàn)冒泡排序的精髓崎岂，下面用三個不同寫法的來實現(xiàn)一個簡單數(shù)列的冒泡排序瘦穆。
首先構造一些公用的方法：
- 構造了一個順序表來存儲待排序數(shù)列
typedef struct {
int nums[MAXSIZE];
int length;
}Sqlist;
- 寫了一個交換數(shù)組元素的方法抡柿，方便交換時直接調用
void swapNums(int i, int j, Sqlist *Sq) {
int temp = Sq->nums[i];
Sq->nums[i] = Sq->nums[j];
Sq->nums[j] = temp;
}
然后就來了：
1. 初級冒泡排序的寫法
void sort(Sqlist *Sq) {
int i,j;
for (i = 0; i<Sq->length; i++) {
for (j = i+1; j<Sq->length; j++) {
printf("這次循環(huán)i=%d,j=%d,相比較的兩個數(shù)：%d %d\n",i,j,Sq->nums[i],Sq->nums[j]);
if (Sq->nums[i] > Sq->nums[j]) {
swapNums(i, j, Sq);
}
}
}
}
2. 正規(guī)的冒泡排序的寫法
void sort2(Sqlist *Sq) {
int i,j;
for (i = 0; i<Sq->length-1; i++) {
for (j = Sq->length-1; j>i; j--) {
printf("這次循環(huán)i=%d,j=%d,相比較的兩個數(shù)：%d %d\n",i,j,Sq->nums[j],Sq->nums[j-1]);
if (Sq->nums[j] < Sq->nums[j-1]) {
swapNums(j, j-1, Sq);
}
}
}
}
以上兩種寫法有什么區(qū)別呢？
寫法的區(qū)別其實就是第二層循環(huán)是倒著循環(huán)的爵赵。以這個數(shù)列為例調用這兩個方法：{4,6,7,5,1,2,3,8,9,10}吝秕。執(zhí)行中第一種方式可能會出現(xiàn)兩個對比的元素不相鄰的情況，而第二種方式一直是相鄰兩元素之間的比較空幻，經過一次次的循環(huán)郭膛，小數(shù)字往上浮，大數(shù)字往下沉氛悬，這就是冒泡排序的精髓所在则剃。
3. 冒泡排序的優(yōu)化
冒泡排序也是可以優(yōu)化的耘柱，當出現(xiàn)例如{10,9,8,1,2,3,4,5,6,7}這樣的數(shù)列，進行升序排序時棍现，從1到7就不用在進行多余的排序了调煎，那么我們在上面第二種方法的基礎上再加上一個標志位，來記錄在某一次循環(huán)中是否出現(xiàn)了交換操作己肮，如果沒有出現(xiàn)士袄，則說明這些元素已經是正確的排序了。代碼如下：
void sort2(Sqlist *Sq) {
int i,j;
int flag = TRUE;
int time = 0;
for (i = 0; i<Sq->length-1 && flag; i++) {
flag = FALSE;
time++;
printf("循環(huán)次數(shù):");
printf("%d\n", time);
for (j = Sq->length-1; j>i; j--) {
printf("這次循環(huán)i=%d,j=%d,相比較的兩個數(shù)：%d %d\n",i,j,Sq->nums[j],Sq->nums[j-1]);
if (Sq->nums[j] < Sq->nums[j-1]) {
swapNums(j, j-1, Sq);
flag = TRUE;
}
}
}
}
二. 選擇排序
升序的排序時谎僻，選擇排序是從第一個元素開始在后面的序列中依次查詢最小的值和其進行交換娄柳。
void sort3(Sqlist *Sq) {
int i,j,min;
for (i = 0; i<Sq->length; i++) {
min = i;
for (j = i+1; j<Sq->length; j++) {
if (Sq->nums[min] > Sq->nums[j]) {
min = j;
}
}
if (min != i) {
swapNums(i, min, Sq);
}
}
}
三. 插入排序
升序排序時，從第二個元素開始艘绍，向前找到這個元素正確的位置
void sort4(Sqlist *Sq) {
int i,j;
int temp = 0;
for (i = 2; i<Sq->length; i++) {
if (Sq->nums[i] < Sq->nums[i-1]) {
temp = Sq->nums[i];
for (j = i-1; Sq->nums[j]>temp; j--) {
Sq->nums[j+1] = Sq->nums[j];
}
Sq->nums[j+1] = temp;
}
}
}
