排序一些基本的排序

浏览数：27 / 时间：2015年06月08日

排序一些基本的排序

约定：在代码中 l，和 r 都是闭区间，例如，有 10 个元素的数组，那么我的代码中 l 和 r 分别是 0 和 9。（使用的是从小到大排序）

冒泡排序
假如有 n 个元素，那我们要走 n-1 次，选择出一个最大，然后丢到后面去。

void bubble(int l, int r) {
     for(int i = l; i <= r-1; i++) {      // n - 1 次
        for(int j = l; j < r-i; j++) {    // 因为 r-i 后面的值都是已经被丢过（排好序）
            if(a[j] > a[j+1]) {
                swap(a, j, j+1);          // 发现大的就开始往后面丢
            }
        }
    }
}

选择排序
和冒泡排序不同的是，选择排序一开是先先选择出最小的，然后开始放到前面。我们要找出一个数组中的最小值。

int min = a[0];
for (int i = 1; i < n; i++) {
    if (a[i] > min) {
        min = a[i];
    }
}

现在我们只需要找到最小值的下标。

int min = 0;
for (int i = 1; i < n; i++) {
    if (a[i] > a[min]) {
        min = i;
    }
}

下面就是选择排序的代码。

void select_sort(int l, int r) {
    for (int i = l; i <= r-1; ++i) {
        int min = i;
        for (int j = i+1; j <= r; ++j) {
            if (a[j] < a[k]) {
                min = j;
            }
        }
        swap(a, k, i);
    }
}

插入排序
插入排序就好像是我们玩扑克牌时候的排序，我们摸到一张牌，那我们就要从右边开始往左边插，（这里假设你是用左手拿着一堆牌，如果你是右手那反过来）。

首先，假设这张牌的大小为 key 且他的下标是 i，那么他要从 i-1 比到 0。j 从 i-1 到 0。如果有比他大的牌，把这张牌的向后推，从 j 推向（j+1）。如果这张牌（j）小于 key，那我们 key 的牌就要放在 j 的后面，也就是 j+1 = key。

void insert_sort(int l, int r) {
    for(int i = l+1; i <= r; i++) {
        int key = a[i];
        int j = i - 1;
        while(j >= 0 && a[j] > key) {
            a[j+1] = a[j];
            j--;
        }
        a[j+1] = key;
    }
}