排序算法

• 内部排序
  • 插入排序：最坏时间复杂度O(n^2)，最佳时间复杂度O(n)，空间复杂度 O(1)
    • 直接插入排序
    • 希尔排序
  • 选择排序
    • 简单选择排序：最坏时间复杂度O(n^{2)，最好时间复杂度O(n}2)，空间复杂度 O(1)
    • 堆排序
  • 交换排序
    • 冒泡排序：最坏时间复杂度O(n^2)，最佳时间复杂度O(n)，空间复杂度 O(1)
    • 快速排序
  • 归并排序：最坏时间复杂度O(nlogn)，最佳时间复杂度O(nlogn)，空间复杂度 O(n)
  • 基数排序
• 外部排序
  不稳定排序：快速排序、希尔排序、选择排序、堆排序
  稳定排序：直接插入排序、冒泡排序、归并排序、计数排序、基数排序、桶排序

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

void print(int * buf, int n)
{
    for(int i = 1; i <= n; ++i)
        printf("%d ", buf[i]);
    printf("\n");
}

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

void buddleSort(int * buf, int n)
{
    for(int i = 1; i < n; ++i)
    {
        bool flag = true;
        if(flag == false)  //如果一次交换也没有，则说明已经有序
            return;
        flag = false;
        for(int j = 1; j <= n-i; ++j)
        {
            if(buf[j] > buf[j+1])
            {
                swap(&buf[j], &buf[j+1]);
                flag = true;
            }
        }
    }
}

void insertSort(int * buf, int n)
{
    for(int i = 2; i <= n; ++i)
    {
        int key = buf[i];
        int j = i - 1;
        
        while(j > 0 && buf[j] > key)
        {
            buf[j+1] = buf[j];
            j--;
        }

        buf[j+1] = key;
    }
}

void chooseSort(int * buf, int n)
{
    for(int i = 1; i < n; ++i)
    {
        int min = i;
        for(int j = i + 1; j <= n; ++j)
        {
            if(buf[min] > buf[j])
            {
                min = j;
            }
        }

        swap(&buf[min], &buf[i]);
    }
}

void merge(int * buf, int low, int mid, int high, int * tmp)
{
    
    int i = low, j = mid + 1, k = low;
    while(i <= mid && j <= high)
    {
        if(buf[i] < buf[j])
            tmp[k++] = buf[i++];
        else
            tmp[k++] = buf[j++];
    }

    while(i <= mid)
        tmp[k++] = buf[i++];
    while(j <= high)
        tmp[k++] = buf[j++];

    for(int i = low; i <= high; ++i)
        buf[i] = tmp[i];
}

void recursive_merge(int * buf, int low, int high, int * tmp)
{
    if(low < high)
    {
        int mid = (low + high) / 2;
        recursive_merge(buf, low, mid, tmp);
        recursive_merge(buf, mid+1, high, tmp);
        merge(buf, low, mid, high, tmp);
    }
}

void mergeSort(int * buf, int n)
{
    if(buf == NULL || n <= 0)
        return;
    int * tmp = (int *)malloc((n+1)*sizeof(int));
    recursive_merge(buf, 1, n, tmp);
}

//两边向中间靠拢
int partition1(int * buf, int low, int high)
{
    int pivot = buf[low];

    while(low < high)
    {
        while(low < high && buf[high] > pivot)
            high--;
        buf[low] = buf[high];

        while(low < high && buf[low] < pivot)
            low++;
        buf[high] = buf[low];
    }

    buf[low] = pivot;

    return low;
}

//单向扫描法
int partition(int a[], int start, int end) {
        int pivot = a[start];  //以首元素为哨兵，用于链表快速排序
        int i = start, j = start+1;  //i 表示在已经遍历的元素中最后一个比pivot小或等的元素
        for(; j <= end; ++j) {
            if(a[j] < pivot) {
                swap(&a[++i], &a[j]);
            }
        }
        
        swap(&a[i], &a[start]);
        return i;
    }

int partition (int a[], int start, int end) {
        int pivot = a[end];
        int i = start-1, j = start;  //i 表示比pivot小或等的元素
        for(; j < end; ++j) {
            if(a[j] < pivot) {
                swap(&a[++i], &a[j]);
            }
        }
        swap(&a[i+1], &a[end]);
        return i+1;
    }
}

void quickSort(int * buf, int left, int right)
{
    if(left < right)
    {
        int mid = partition1(buf, left, right);
        quickSort(buf, left, mid-1);
        quickSort(buf, mid+1, right);
    }   
}

int main()
{
    freopen("in.txt", "r", stdin);

    int n;
    while(scanf("%d", &n) != EOF)
    {
        int * buf = (int *) malloc((n+1) * sizeof(int));
        for(int i = 1; i <= n; ++i)
        {
            scanf("%d", buf+i);
        }
        //buddleSort(buf, n);
        //insertSort(buf, n);
        //chooseSort(buf, n);
        //mergeSort(buf, n);
        quickSort(buf, 1, n);

        print(buf, n);

        free(buf);
    }

    return 0;
}