2014-06-11 六种排序方式 sort.c

---

1. 选择排序 select_sort

void select_sort(int* arr, int len)
{
    int i, j;
    for(i = 0; i < len - 1; i++)
    {
        int min = i;
        for(j = i + 1; j < len; j++)
        {
            if(arr[min] > arr[j])
                min = j;
        }
        if(min != i)
            _swap(&arr[i], &arr[min]);
    }
}

---

2. 插入排序 insert_sort

void insert_sort(int* arr, int len)
{
    int i, j, flag, tmp;
    for(i = 1; i < len; i++)
    {
        for(j = i; j > 0; j--)
        {
            if(arr[j - 1] < arr[i])
                break;
        }
        flag = j;
        if(flag != i)
        {
            tmp = arr[i];
            for(j = i; j > flag; j--)
            {
                arr[j] = arr[j - 1];
            }
            arr[j] = tmp;
        }
    }
}

---

3. 冒泡排序 bubble_sort

void bubble_sort(int* arr, int len)
{
    int i, j;
    for(i = 0; i < len - 1; i++)
    {
        for(j = len; j > i; j--)
        {
            if(arr[j] < arr[j - 1])
                _swap(&arr[j], &arr[j - 1]);
        }
    }
}

---

4. 快速排序 quick_sort

/* 
 * 分治Partition，
 * 两个下标分别从首尾向中间扫描 
 */
int partition(int* arr, int len)    
{
    int left = 0, right = len - 1;
    int pivot = arr[left];   //以当前表中第一个元素为枢轴值进行划分
    while(left < right)   //结束条件
    {
        while(left < right && arr[right] >= pivot)
            right--;
        arr[left] = arr[right];   //比枢轴值小的元素移动到左端
        while(left < right && arr[left] < pivot)
            left++;
        arr[right] = arr[left];   //比枢轴值大的元素移动到右端
    }
    arr[left] = pivot;   //枢轴元素放到最终位置
    return left;     //返回该位置
}
void quick_sort(int* arr, int len)
{
    if(len > 0)
    {
        int part = partition(arr, len); 
        quick_sort(arr, part);
        quick_sort(arr + part + 1, len - part - 1);
    }
}

---

5. 堆排序 heap_sort

/* 
 * 本函数功能是：根据数组 arr 构建大根堆
 *      arr 是待调整的堆数组，
 *      i 是待调整的数组元素的位置，
 *      len 是数组的长度
 */
void heap_adjust(int* arr, int i, int len)
{
    int child;
    for(; 2*i+1 < len; i = child)
    {
        child=2*i+1;    //子结点的位置=2*（父结点位置）+1
        if(child < len-1 && arr[child+1] > arr[child])  //得到子结点中较大的结点
            ++child;
        if(arr[i] < arr[child]) 
            //如果较大的子结点大于父结点那么把较大的子结点往上移动，替换它的父结点
            _swap(&arr[i], &arr[child]);
        else    //否则，不需要再向下调整，直接跳出
            break;
    }
}
/* 
 * 堆排序算法
 */
void heap_sort(int* arr, int len)
{
    //调整序列的前半部分元素，调整完之后第一个元素是序列的最大的元素
    //length/2-1是最后一个非叶节点，此处"/"为整除
    for(int i = len/2-1; i >= 0; --i)
        heap_adjust(arr, i, len);
    //从最后一个元素开始对序列进行调整，不断的缩小调整的范围直到第一个元素
    for(int i = len-1; i > 0; --i)
    {
        //把第一个元素和当前的最后一个元素交换，
        //保证当前的最后一个位置的元素都是在现在的这个序列之中最大的
        _swap(&arr[0], &arr[i]);
        //不断缩小调整heap的范围，每一次调整完毕保证第一个元素是当前序列的最大值
        heap_adjust(arr, 0, i);
    }
}

---

6. 归并排序

/* 
 * 归并：
 *    将有两个有序数组
 *      a[first ... mid], 
 *      a[mid ... last]
 *    合并
 */
void mergearray(int arr[], int first, int mid, int last, int temp[])
{
    int i = first, j = mid + 1; 
    int k = 0;  
    while (i <= mid && j <= last) 
        //两边都有元素时，进行比较，将较小元素存入临时数组
    {  
        if (arr[i] <= arr[j])  
            temp[k++] = arr[i++];  
        else  
            temp[k++] = arr[j++];  
    }  
    while (i <= mid)  //剩下一个数组可能还存在多余元素，直接存入临时数组
        temp[k++] = arr[i++];  
    while (j <= last)  //同上
        temp[k++] = arr[j++];  
    for (i = 0; i < k; i++)  //将临时数组中的有序数赋给原数组
        arr[first + i] = temp[i];  
} 
/*
 * 归并排序算法
 */
void mergesort(int arr[], int first, int last, int temp[]) 
{  
    if (first < last)
    {  
        int mid = (first + last) / 2;  
        mergesort(arr, first, mid, temp);    //左边有序
        mergesort(arr, mid + 1, last, temp); //右边有序
        mergearray(arr, first, mid, last, temp); //再将两个有序数列合并
    }
}
bool merge_sort(int arr[], int len)  
{  
    int *p = new int[len]; 
        //在此处开辟临时数组，
        //防止在算法中多次开辟和删除临时数组造成的开销（耗时）过大
    if (p == NULL)  
        return false;  
    mergesort(arr, 0, len - 1, p); 
    delete[] p;  
    return true;  
}  

---

50个随机数测试

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define SIZE 50
void _swap(int* a, int* b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}
void print(int* arr, int len)
{
    int i;
    for(i = 0; i < len; i++)
    {
        printf("%4d", arr[i]);
        if((i + 1)%10 == 0)
            printf("\n");
    }
}
int main()
{
    srand(time(NULL));
    int arr[SIZE];
    int i;
    for(i = 0; i < SIZE; i++)
    {
        arr[i] = rand()%1000;
    }
    printf("before sort:\n");
    print(arr, SIZE);
    printf("\n");
    //select_sort(arr, SIZE);
    //insert_sort(arr, SIZE);
    //bubble_sort(arr, SIZE);
    //quick_sort(arr, SIZE);
    //heap_sort(arr, SIZE);
    merge_sort(arr, SIZE);
    printf("after sort:\n");
    print(arr, SIZE);
    return 0;
}

---