• 內(nèi)部排序
  • 插入排序：最壞時間復(fù)雜度O(n^2)，最佳時間復(fù)雜度O(n)初茶，空間復(fù)雜度 O(1)
    • 直接插入排序
    • 希爾排序
  • 選擇排序
    • 簡單選擇排序：最壞時間復(fù)雜度O(n^{2)壕吹，最好時間復(fù)雜度O(n}2)，空間復(fù)雜度 O(1)
    • 堆排序
  • 交換排序
    • 冒泡排序：最壞時間復(fù)雜度O(n^2)辉哥，最佳時間復(fù)雜度O(n)桦山，空間復(fù)雜度 O(1)
    • 快速排序
  • 歸并排序：最壞時間復(fù)雜度O(nlogn)，最佳時間復(fù)雜度O(nlogn)醋旦，空間復(fù)雜度 O(n)
  • 基數(shù)排序
• 外部排序
  不穩(wěn)定排序：快速排序恒水、希爾排序、選擇排序饲齐、堆排序
  穩(wěn)定排序：直接插入排序钉凌、冒泡排序、歸并排序捂人、計數(shù)排序御雕、基數(shù)排序、桶排序

#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)  //如果一次交換也沒有滥搭，則說明已經(jīng)有序
            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 表示在已經(jīng)遍歷的元素中最后一個比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;
}