排序_交换排序（冒泡排序&快速排序）

冒泡排序：相邻元素的交换

基本思路：每趟不断将相邻两个元素两两比较，并按“前小后大” 规则交换。
优点：每趟结束时，不仅能挤出一个最大值到最后面位置，还能同时部分理顺其他元素；一旦下趟没有交换发生，还可以提前结束排序。

实现代码：

static void BubbleSortAsc(int[] array)
{
    int temp;
    for (int i = 0; i < array.Length - 1; i++)
    {
        for (int j = 0; j < array.Length - i- 1; j++)
        {
            if (array[j] > array[j + 1])
            {
                temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }
}

总结：
1、最好情况：初始序列已经有序，只作比较，不移动对象；最差情况：初始序列逆序。
2、时间复杂度：O(n²) ——因为要考虑最坏情况。
3、稳定性：稳定，因为相同元素前后次序不会改变。

---

快速排序：跳跃式的交换

基本思想：
1、任取一个元素作为标准（如取第一个元素）, 按照该对象值的大小,将整个序列划分为左右两个子序列。标准元素排在这两个子序列中间(这也是该对象最终应安放的位置)。
2、然后分别对这两个子序列重复施行上述方法（递归），直到所有的对象都排在相应位置上为止。

例子：

1、i 标记第一个位置，j 标记最后一个位置；
2、获取标准元素21（第一个元素）；
3、从 j 开始往前遍历，遇到小于21则将该元素赋值给i位置，i+1，退出遍历；
4、从i位置往后遍历，遇到大于21则将该元素移到j位置，j-1，退出遍历；
5、重复3、4步，直到i = j，把21塞回来。

实现代码：

static void QuickSort(int[] a, int left, int right)
{
    int i = left;
    int j = right;
    int temp = a[left];
    while (i < j)
    {
        //右端往前遍历，遇到小于标准元素temp则退出循环
        while (i < j && temp <= a[j])
            j--;
        if (i < j)//排除i=j退出循环的情况
        {
            a[i] = a[j];
            i++;
        }
        //左端遍历
        while (i < j && temp > a[i])
            i++;
        if (i < j)
        {
            a[j] = a[i];
            j--;
        }

    }
    a[i] = temp;
    if (left < i) QuickSort(a, left, i - 1);
    if (right > i) QuickSort(a, i + 1, right);
}

总结：
1、因为每趟可以确定不止一个元素的位置，而且呈指数增加，所以特别快。
2、时间效率：O(nlog2n) —因为每趟确定的元素呈指数增加