排序算法

常见的排序算法有：

• 冒泡排序
• 快速排序
• 插入排序
• 归并排序
• 堆排序

1. 冒泡排序

冒泡排序是一种极其简单的排序算法，也是我所学的第一个排序算法。它重复地走访过要排序的元素，依次比较相邻两个元素，如果他们的顺序错误就把他们调换过来，直到没有元素再需要交换，排序完成。

优点:比较简单，空间复杂度较低，是稳定的
缺点:时间复杂度太高，效率不高

算法实现：

//冒泡排序
// 分类 -------------- 内部比较排序
// 数据结构 ---------- 数组
// 最差时间复杂度 ---- O(n^2)
// 最优时间复杂度 ---- 如果序列在一开始已经大部分排序过的话,会接近O(n)
// 平均时间复杂度 ---- O(n^2)
// 所需辅助空间 ------ O(1)
// 稳定性 ------------ 稳定
void HelloWorld::bubbleShort(int items[], int count) {
    for (int i = 0; i < count - 1; i++)
    {
        for (int j = 0; j < count - 1 - i; j++)
        {
            if (items[j] > items[j + 1])  // 如果条件改成items[j] >= items[j+1],则变为不稳定的排序算法
            {
                int temp;
                temp = items[j + 1];
                items[j + 1] = items[j];
                items[j] = temp;
            }
        }
    }
}

1. 快速排序

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序n个元素要O(nlogn)次比较。在最坏状况下则需要O(n^2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他O(nlogn)算法更快，因为它的内部循环可以在大部分的架构上很有效率地被实现出来。

快速排序使用分治策略(Divide and Conquer)来把一个序列分为两个子序列。步骤为:

1. 从序列中挑出一个元素，作为"基准"(pivot).
2. 把所有比基准值小的元素放在基准前面，所有比基准值大的元素放在基准的后面（相同的数可以到任一边），这个称为分区(partition)操作。
3. 对每个分区递归地进行步骤1~2，递归的结束条件是序列的大小是0或1，这时整体已经被排好序了。

优点：极快，数据移动少；   
缺点：不稳定。 
算法实现：

#include <iostream>

// 分类 ------------ 内部比较排序
// 数据结构 --------- 数组
// 最差时间复杂度 ---- 每次选取的基准都是最大（或最小）的元素，导致每次只划分出了一个分区，需要进行n-1次划分才能结束递归，时间复杂度为O(n^2)
// 最优时间复杂度 ---- 每次选取的基准都是中位数，这样每次都均匀的划分出两个分区，只需要logn次划分就能结束递归，时间复杂度为O(nlogn)
// 平均时间复杂度 ---- O(nlogn)
// 所需辅助空间 ------ 主要是递归造成的栈空间的使用(用来保存left和right等局部变量)，取决于递归树的深度，一般为O(logn)，最差为O(n)       
// 稳定性 ---------- 不稳定

void Swap(int array[], int i, int j)
{
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

int Partition(int array[], int left, int right)  // 划分函数
{
    int pivot = array[right];               // 这里每次都选择最后一个元素作为基准
    int tail = left - 1;                // tail为小于基准的子数组最后一个元素的索引
    for (int i = left; i < right; i++)  // 遍历基准以外的其他元素
    {
        if (array[i] <= pivot)              // 把小于等于基准的元素放到前一个子数组末尾
        {
            Swap(array, ++tail, i);
        }
    }
    Swap(array, tail + 1, right);           // 最后把基准放到前一个子数组的后边，剩下的子数组既是大于基准的子数组
                                        // 该操作很有可能把后面元素的稳定性打乱，所以快速排序是不稳定的排序算法
    return tail + 1;                    // 返回基准的索引
}

void QuickSort(int array[],int left,int right) {
    if (left >= right) {
        return;
    }

    int pivot_index = Partition(array, left, right); // 基准的索引
    QuickSort(array, left, pivot_index - 1);
    QuickSort(array, pivot_index + 1, right);
}

int main()
{
    int array[] = {1,3,45,6,8,3,7,0,1,7,9};
    int count = sizeof(array) / sizeof(array[0]);
    QuickSort(array,0,count-1);

    for (int i = 0; i < count; i++)
    {
        printf("%d \n", array[i]);
    }

    printf("++++++++");
    return 0;
}