八大排序算法之交换排序

标签: 排序

在之前两篇文章中,我们学习了插入排序和选择排序,八大算法之插入排序八大算法之选择排序,这篇文章,我们来了解一下交换排序。
常用的交换排序有冒泡排序和快速排序,主要思想就是交换。

1.冒泡排序

基本思想:每相邻两个数比较,若大小与要排序顺序不同,则交换。
将序列当中的左右元素,依次比较,保证右边的元素始终大于左边的元素( 第一轮结束后,序列最后一个元素一定是当前序列的最大值;)
对序列当中剩下的n-1个元素再次执行以上步骤。

时间复杂度:O(N^2)

空间复杂度:O(1)
这里写图片描述

void BubbleSort(int a[],int n)
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n - i - 1; j++)
        {
            if (a[j]>a[j + 1])
                swap(a[j], a[j + 1]);
        }
    }
}
2.快速排序

基本思想:挖坑填数+分治法
从序列当中选择一个基准数
在这里我们选择序列当中第一个数最为基准数
将序列当中的所有数依次遍历,比基准数大的位于其右侧,比基准数小的位于其左侧
重复步骤1.2,直到所有子集当中只有一个元素为止。

时间复杂度:O(Nlog2N)
空间复杂度:O(N) N为递归压栈次数
这里写图片描述

void QuickSort(int a[], int l, int r)
{
    if (l< r)
    {
        int i = l, j = r, x = a[l];
        while (i < j)
        {
            while (i < j && a[j] >= x) // 从右向左找第一个小于x的数
                j--;
            if (i < j)
                a[i++] = a[j];
            while (i < j && a[i]< x) // 从左向右找第一个大于等于x的数
                i++;
            if (i < j)
                a[j--] = a[i];
        }
        a[i] = x;
        QuickSort(a, l, i - 1); // 递归调用
        QuickSort(a, i + 1, r);
    }
}

对快速排序来说,两个指针分别查找相较于基准值大或者小的,所以相同元素的相对位置可能会发生改变,即快排是不稳定的。

原文链接:加载失败,请重新获取