首页 > 代码库 > 排序算法总结

排序算法总结

1. 快排

详见之前博文快速排序算法。

2. 堆排序

详见之前博文非递归方法的堆排序实现。

3. 简单排序(冒泡排序、选择排序和插入排序)

代码如下:

#include <stdio.h>#include <stdlib.h>#include <time.h>#define N 20static void show(int *arr, int len){    int index;    for(index = 0; index < len; index++)    {        printf("%d ", arr[index]);    }    printf("\n");}static void swap(int *left, int *right){    int tmp = *left;    *left = *right;    *right = tmp;}/** * 选择排序思想:依次将未排序的数组中的最小数放入pos所在位置,pos从0至N-1 * -->前N-1个数放好位置,最后一个数就不用管了 */static void select_sort(int *arr, int len){    int pos,index;    int min_index;    for(pos = 0; pos < len - 1; pos++)    {        min_index = pos;        for(index = pos + 1; index < len; index++)        {            if(arr[index] < arr[min_index])                min_index = index;        }        if(min_index != pos)        {            swap(arr + pos, arr + min_index);        }    }}static void insert_sort(int *arr, int len){    int pos,index;    int key;    for(pos = 1; pos < len; pos++)    {        key = arr[pos];        for(index = pos - 1; index >= 0; index--)        {            if(key < arr[index])            {                arr[index+1] = arr[index];            }else            {                break;            }        }        arr[index+1] = key;    }}static void bubble_sort(int *arr, int len){    int pos,index;    for(pos = 0; pos < len - 1; pos++)    {        for(index = 0; index < len - 1 - pos; index++)        {            if(arr[index] > arr[index + 1])            {                swap(arr + index, arr + index + 1);            }        }    }}static void bubble_sort2(int *arr, int len){    int left, right, index;    left = 0;    right = len - 1;    while(left < right)    {        for(index = left; index < right; index++)        {            if(arr[index] > arr[index+1])            {                swap(arr+index, arr+index+1);            }        }        right--;        if(left == right)        {            break;        }        for(index = right; index > left; index--)        {            if(arr[index] < arr[index-1])            {                swap(arr + index, arr + index -1);            }        }        left++;    }}int main(int argc, char *argv[]){    int arr[N], index;    srand(time(NULL));    for(index = 0; index < N; index++)    {        arr[index] = rand()%100 + 1;    }    show(arr, N);    bubble_sort2(arr, N);    show(arr, N);    system("pause");    return 0;}

4. 归并排序

待续。

排序算法总结