C++复习之排序

排序有很多种，这里记录一下经常会用到的：插入排序（直接、二分法、希尔排序）、交换排序（冒泡、快排）、选择排序（简单选择排序、堆排序）、归并排序、基数排序、外部排序，先说前三种。
什么叫排序算法是稳定的？比如：{3,5,7,7,2}，如果排完序原来第一个7仍然在第二个7前面，则是稳定的，否则，则是不稳定的。

int main()
{
    int sorted[10] = { 8,5,3,9,7,11,41,33,22,14 };
    cout << "输出待排序数组：" << endl;
    for (int p = 0;p < 10;p++)
    {
        cout << sorted[p]<<endl;
    }
//.......排序算法
    cout << "排序数组：" << endl;
    for (int p = 0;p < 10;p++)
    {
        cout << sorted[p] << endl;
    }
    system("pause");
    return 0;

1.直接插入排序：时间复杂度O（n^2）,稳定。

int i, j;
    for (i = 1;i < n;i++)
    {
        int temp = sorted[i];
        j = i - 1;
        while (j >= 0 && temp < sorted[j])
        {
            sorted[j + 1] = sorted[j];
            j--;
        }
        sorted[j + 1] = temp;
    }

2.二分法插入排序，时间复杂度O（n^2）,稳定

//二分法插入排序
    int left, right, mid,temp;
    for (int p = 1;p < 10;p++)
    {
        temp = sorted[p];
        left = 0;
        right = p-1;        
        while (left <= right)
        {
            mid = (right + left) / 2;
            if (temp < sorted[mid])
                right = mid-1;
            else
                left = mid+1;
        }
        for (int i = p - 1;i >= left;i--)
        {
            sorted[i + 1] = sorted[i];
        }
        sorted[left] = temp;
    }

3.冒泡排序：O（n^2）,稳定

//冒泡排序
    int flag = 0;
    for (int i = 0;i < 10;i++)
    {
        for (int j = 1;j < 10 - i;j++)
        {
            if (sorted[j] < sorted[j - 1])
            {
                flag = 1;
                int tempt = sorted[j];
                sorted[j] = sorted[j - 1];
                sorted[j - 1] = tempt;
            }
        }
        if (flag == 0)
            break;
    }

4.快排：分割、分治、合并，时间复杂度O(nlogn),不稳定

int partition(int sorted[], int left, int right)
{

    int pivot = sorted[left];
    while (left < right)
    {
        while (left<right && sorted[right]>pivot)
            right--;
        sorted[left] = sorted[right];
        while (left < right && sorted[left] <= pivot)
            left++;
        sorted[right] = sorted[left];
    }
    sorted[left] = pivot;
    return left;
}
void Quicksort(int sorted[], int left, int right)
{

    if (left < right)
    {
        int p = partition(sorted, left, right);
        Quicksort(sorted, left, p - 1);
        Quicksort(sorted, p + 1, right);
    }
}
//快速排序
    Quicksort(sorted, 0, 9);

5.简单选择排序：O(n^2),不稳定

    //简单选择排序
    for (int i = 1;i < 10;i++)
    {
        int k = i - 1;
        for (int j = i;j < 10;j++)
        {
            if (sorted[k] > sorted[j])
                k = j;
        }
        if (k != i - 1)
        {
            int tempt = sorted[k];
            sorted[k] = sorted[i-1];
            sorted[i - 1] = tempt;
        }
    }