选择、冒泡、快速排序

sort.c

#include <stdio.h>

// swap 函数
void swap(int *a,  int *b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

// 选择排序
void selection_sort(int data[], const int size){
    int i, j, tmp, min; 
    for (i = 0; i < size - 1; i++) {
        // find the minimum
        min = i;
        for (j = i; j < size; j++) {
            if (data[j] < data[min]) {
                min = j;
            }
        }
        // swap data[i] and data[min]
        tmp = data[i];
        data[i] = data[min];
        data[min] = tmp;
    }
}

// 冒泡排序
void bubble_sort(int a[], const int size) {
    int flag = 1;
    int i, j, temp = 0;
    for (i = 0; i < size - 1; i++) {
        flag = 1;
        for (j = 0 ; j < size - i - 1 ; j++) {
            if (a[j] > a[j + 1]) {
                // swap a[j] and a[j+1]
                temp = a[j + 1];
                a[j + 1] = a[j];
                a[j] = temp;
                flag = 0;
            }
        }
        if (flag == 1) {
            // 一次循环无交换行为
            break;
        }
    }
}

// 快速排序
void quick_sort(int a[], int l, int r) {
    int i = l;
    int j = r;
    int temp;
    // 取数组中间值为参考点
    int key = a[(i + j) / 2];
    // 将比key小的元素放到key的左边，比key大的元素放到key的右边
    while(i < j) {
        // 取左数第一个比key大的元素标号为i
        for(; (i < r) && (a[i] < key); i++);
        // 取右数第一个比key小的元素标号为j
        for(; (j > l) && (a[j] > key); j--);
        if (i <= j){
            // 交换 a[i] 和 a[j]
            if(i != j) {
                temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
            // 压缩比较范围
            i++;
            j--;
        }
    }
    // 循环结束后i >= j
    // 比较key右方区域
    if (i < r)
        quick_sort(a, i, r);
    // 比较key左方区域
    if (j > l)
        quick_sort(a, l, j);
}

int main(int argc, const char *argv[]) {
    int data[] = {4, 6, 8, 2, 13, 12, 1, 4};
    int size = sizeof(data) / sizeof(int);
    int i;
    //selection_sort(data, size);
    //bubble_sort(data, size);
    //quick_sort(data, 0, size - 1);

    for (i = 0; i < size; i++) {
        printf("%d ", data[i]);
    }
    printf("\n");
    return 0;
}