常用的排序算法

一. 冒泡排序

我们常常在写冒泡排序的时候会将待排序数列从第一个元素开始依次和后面的每一个元素进行比对和交换，但是这种做法并没有体现冒泡排序的精髓，下面用三个不同写法的来实现一个简单数列的冒泡排序。
首先构造一些公用的方法：

构造了一个顺序表来存储待排序数列

typedef struct {
    int nums[MAXSIZE];
    int length;
}Sqlist;

写了一个交换数组元素的方法，方便交换时直接调用

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("这次循环i=%d,j=%d,相比较的两个数：%d %d\n",i,j,Sq->nums[i],Sq->nums[j]);
            if (Sq->nums[i] > Sq->nums[j]) {
                swapNums(i, j, Sq);
            }
        }
    }
}

2. 正规的冒泡排序的写法

void sort2(Sqlist *Sq) {
    int i,j;       
    for (i = 0; i<Sq->length-1; i++) {
                      
        for (j = Sq->length-1; j>i; j--) {
            printf("这次循环i=%d,j=%d,相比较的两个数：%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);
            }
        }
    }
}

以上两种写法有什么区别呢？
写法的区别其实就是第二层循环是倒着循环的。以这个数列为例调用这两个方法：{4,6,7,5,1,2,3,8,9,10}。执行中第一种方式可能会出现两个对比的元素不相邻的情况，而第二种方式一直是相邻两元素之间的比较，经过一次次的循环，小数字往上浮，大数字往下沉，这就是冒泡排序的精髓所在。

3. 冒泡排序的优化

冒泡排序也是可以优化的，当出现例如{10,9,8,1,2,3,4,5,6,7}这样的数列，进行升序排序时，从1到7就不用在进行多余的排序了，那么我们在上面第二种方法的基础上再加上一个标志位，来记录在某一次循环中是否出现了交换操作，如果没有出现，则说明这些元素已经是正确的排序了。代码如下：

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("循环次数:");
        printf("%d\n", time);
        
        for (j = Sq->length-1; j>i; j--) {
            printf("这次循环i=%d,j=%d,相比较的两个数：%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;
        }
        
    }
}