常见排序算法-----很多不理解！！！

  估计是自己太笨，老觉得用算法实现排序很难。当然简单的好懂，稍微复杂的就懵了。唉，只有“烂笔头”了看来。

 

/*
 ============================================================================
 Name : sort.c
 Author : hl
 Version :
 Copyright : Your copyright notice
 Description : sorting in C, Ansi-style
 ============================================================================
 */

#include <stdio.h>
#include <stdlib.h>
#include "sort.h"

/*
 * 打印整型数组
 */
void print_array(int a[], int len)
{
    int i;
    for (i = 0; i < len; i++)
        printf("%d ", a[i]);
    putchar('\n');
}

/*
 * 冒泡排序: 时间复杂度（ n^2) 稳定----相同元素排序和位置不变
 * 说明:
 *     1.注意i < len - 1，而不是i < len（
 *      如果你写成了i < len或许对，而且不会报数组访问越界（那是因为编译器不检查），但是是错的。
 * ）；
 * 2.关于冒泡排序的改进就是增加标志位；
 * 3.数据量大的时候改用快速排序;
 */
void bubble(int a[], int len)
{
    int i, j;
    int temp;

    int flag;

    for (i = 0; i < len - 1; i++)
    {
        print_array(a, len);
        flag = 1;
        for (j = 0; j < len - i - 1; j++)
        {
            if (a[j] > a[j + 1])
            {
                temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;

                flag = 0;
            }
        }
        if (1 == flag) //表示经过一轮比较后没有进行交换，因此跳出
            break;
    }
}

/*
 * 快速排序: 时间复杂度（最好情况下 O(nlgn)，最坏情况下 n^2)
 * 说明:
 *     1.冒泡排序的改进, 原地排序；
 */
int partitions(int a[], int low, int high)
{
    int key = a[low];
    while (low < high)
    {
        while (low < high && a[high] >= key)
            high--;
        a[low] = a[high];
        while (low < high && a[low] <= key)
            ++low;
        a[high] = a[low]; //有时候 low == high(++low之后)
    }
    a[low] = key;
    return low; //从上面可以看出，Key只是作为标准；最终目是把比它小的放在前面，比它大的放在后面，利用交换实现；
}

void qsort_e(int a[], int low, int high)
{
    int mid;
    if (low < high)
    {
        mid = partitions(a, low, high);
        qsort_e(a, low, mid - 1);
        qsort_e(a, mid + 1, high);
    }
}

/*
 * 插入排序: 时间复杂度（最好情况下 n，最坏情况下 n^2)
 * 说明:
 *     1.插入排序最好情况an + b和最坏情况an^2 + bn + c 的推导过程；
 *     2.当n足够大时，（an^2 + bn + c）夹在c1n^2 和 c2n^2 之间的证明推理；
 */
void insertion_sort(int a[], int len)
{
    int j = 0, i = 0;
    int key = 0;
    for (j = 1; j < len; j++)
    {
        print_array(a, len);

        key = a[j];
        i = j - 1;
        while (i >=0 && a[i] > key)
        {
            a[i + 1] = a[i];
            i--;
        }
        a[i + 1] = key;
    }
    print_array(a, len);
}

/*
 * 归并排序: 时间复杂度（nlogn)
 * 说明:
 *     1.插入排序最好情况n时，比归并排序效率高；
 * 2.采用分而治之的策略；（自己还是很难想透，感觉拿来用就是了。）
 */
void merge(int start, int mid, int end, int a[], int len)
{
    //分割左右两部分
    int n1 = mid - start + 1;
    int n2 = end - mid;
    int left[n1], right[n2];

    int i, j, k;
    for (i = 0; i < n1; i++) /* left holds a[start..mid] */
    {
        left[i] = a[start + i];
    }
    for(j = 0; j < n2; j++) /* right holds a[mid+1..end] */
    {
        right[j] = a[mid + 1 + j];
    }

    i = j = 0;
    k = start;
    while (i < n1 && j < n2)
    {
        if (left[i] < right[j])
            a[k++] = left[i++];
        else
            a[k++] = right[j++];
    }
    while (i < n1) /* left[] is not exhausted */
        a[k++] = left[i++];
    while (j < n2) /* right[] is not exhausted */
        a[k++] = right[j++];
}

void merge_sort(int start, int end, int a[], int len)
{
    int mid;
    if (start < end)
    {
        mid = (start + end) / 2;
        print_array(a, len);
        merge_sort(start, mid, a, len);
        merge_sort(mid + 1, end, a, len);
        merge(start, mid, end, a, len);
        print_array(a, len);
    }
}

int main(void) {
#if 0
    int a[LEN] = {10, 5, 2, 4, 7};
    insertion_sort(a, LEN);
#endif
#if 0
    int a1[8] = {5, 2, 4, 7, 1, 3, 2, 6};
    merge_sort(0, 7, a1, 8);
#endif
#if 0
    int a2[LEN] = {10, 5, 6, 3, 7};
    bubble(a2, LEN);
#endif
    int a3[7] = {49, 38, 65, 97, 76, 13, 27};
    print_array(a3, LEN + 2);
    qsort_e(a3, 0, 6);
    print_array(a3, LEN + 2);

    return EXIT_SUCCESS;
}