几种基础排序算法

1、选择排序

选择排序是一种直观简单的排序算法，它每次从待排序的数据元素中选出最小(或者最大)元素存放到序列的起始位置，直到全部待排序的数据元素排完。注意，选择排序并不是稳定的排序。

void selectsort(int arr[ ], int length)
{
    for(int i = 0; i < length; i ++)
    {
        int min = i;
        for(int j = i + 1;j < length; j ++)
        {
            if(arr[min] < arr[j])
            {
                min = j;
            }
        }
        if(min != i)
        {
            swap(arr[min], arr[i]);
        }
    }
} 

 2、冒泡排序

冒泡排序也是一种直观简单的排序算法，它重复地走访要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。冒泡排序是一种稳定的排序。

 

void bubblesort(int arr[],int length)
{
    for(int i = 0; i < length; i ++ )
    {
        for(int j = 0; j < length - i - 1; j ++ )
        {
            if(arr[j] > arr[j + 1])
            {
                swap(arr[j], arr[j + 1];
            }
        }
    }
}

3、插入排序

插入排序基本思想是：每步将一个待排序的纪录，按其关键码值的大小插入前面已经排序的元素序列中适当位置上，直到全部插入完为止。插入排序是稳定的排序算法。

void insertsort(int arr[], int length)
{
    for(int i = 0; i < length; i ++ )
    {
        for(int j = i; j > 0 && arr[j - 1] > arr[j]; j -- )
        {
            swap(arr[j], arr[j - 1]);
        }
    }
}

 4、希尔排序

希尔排序(Shell Sort)是插入排序的一种，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个数组恰被分成一组，算法便终止。

void ShellSort(int arr[], int length)
{
    for (int inc = length / 2; inc > 0; inc /= 2) 
    {
        for (int i = inc; i < length; i++) 
        {
        	for (int j = i; j >= inc && arr[j - inc] > arr[j]; j -= inc)
            {
                swap(arr[j], arr[j - inc]);
            }
        }
    }
}

 5、快速排序

快速排序的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

void quick_sort(int q[], int l, int r)
{
    if(l >= r) return ;
    int i = l - 1, j = r + 1, x = q[l];
    while(i < j)
    {
        do i++; while(q[i] < x);
        do j --; while(q[j] > x);
        if(i < j) swap(q[i], q[j]);
        else break;
    }
    quick_sort(q, l, j), quick_sort(q, j + 1, r);
}

 6、归并排序

归并排序是将两个有序的数组归并成一个更大的有序数组。要将一个数组排序，可以先（递归的）将他分成两半分别排序，让后将结果归并起来。它能够保证将任意长度为N的数组排序所需时间和NlogN成正比；它的主要缺点就是所需的额外空间和N成正比。归并排序是稳定的排序算法。

void merge_sort(int q[], int l, int r)
{
    if(l >= r) return;
    int mid = l + r >> 1;
    mergr_sort(q, l, mid),merge_sort(q, mid + 1, r);
    int k = 0, i = l, j = mid + 1;
    while(i <= mid && j = mid + 1)
    if(q[i] < q[j]) tmp[k ++] = q[i ++];
    else tmp[k ++] = q[j ++];
    while(i <= mid) tmp[k ++] = q[i ++];
    while(j <= r) tmp[k ++] = q[j ++];
    for(i = l, j = 0; i <= r; i ++, j++) q[i] = tmp[j];
}