1.冒泡排序

bubbleSort.gif

//冒泡排序 比较两个相邻元素，大的放后面
//每一轮都会把该轮最大值的放后面
void pop_sort(int arr[], int len) {
    int temp;
    //len-1的原因是  两个元素只需要排一趟，len个元素只需len-1趟
    for (int i = 0; i < len-1; i++) {
        for (int j = 0; j < len-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                temp = arr[j + 1];
                arr[j + 1] = arr[j];
                arr[j] = temp;
            }
        }
    }
}

2.选择排序

selectionSort.gif

//选择排序，每次在未排序的元素中找到最大值/最小值放到末尾/开头
//只需将最小/大的元素和末尾/开头元素调换位置
//最小
void chose_sort1(int arr[], int len) {
    int min;
    for (int i = 0; i < len - 1; i++) {
        min = i;
        for (int j = i+1; j < len; j++) {
            if (arr[j] < arr[min]) {
                min = j;
            }
        }
        int temp;
        temp = arr[i];
        arr[i] = arr[min];
        arr[min] = temp;
    }
}

//最大
void chose_sort2(int arr[], int len) {
    int max;
    for (int i = 0; i < len - 1; i++) {
        max = len-i-1;
        for (int j = 0; j < len-i-1; j++) {
            if (arr[j] >arr[max]) {
                max = j;
            }
        }
        int temp;
        temp = arr[len-i-1];
        arr[len-i-1] = arr[max];
        arr[max] = temp;
    }
}

3.插入排序

将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

insertionSort.gif

//插len-1趟，初始化，第一个元素当初被排序过的序列，从头到尾扫描没被排序的序列，将其插入到排序的序列中,
//特别注意尾部开始插入 头插的话太麻烦
void insert_sort(int arr[], int len) {
         //i表示当前要插入的元素，从第二个元素开始
    for (int i = 1; i < len; i++) {
        int key = arr[i];//要插入的元素
        int j = i - 1;//j表示已排序序列的最后一位
        while (j >= 0 &&key<arr[j]) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j+1] = key;

    }
}

4.希尔排序

Sorting_shellsort_anim.gif

//先取一个小于n的整数d1作为第一个增量，把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；
//一般的初次取序列的一半为增量，以后每次减半，直到增量为1
void shell_sort(int arr[], int len) {
    int d = len / 2;
    while (d) {
        for (int i = d; i< len; i++) {
            int key = arr[i];
            int j = i-d;
            while (j >= 0 && key < arr[j]) {
                arr[j+d] = arr[j];
                j=j-d;
            }
            arr[j + d] = key;
        }
        d = d / 2;
    }   
}