老青菜

交换排序

2019-04-01

交换排序是一种简单的排序算法,属于比较类排序,内部是通过比较元素大小,交换位置,最终达到列表有序。
常见的主要有两种:

  1. 冒泡排序(BubbleSort
  2. 快速排序(QuickSort


冒泡排序

冒泡排序(BubbleSort)原理如下:

  1. 比较相邻的元素,大的往后移动,交换元素。
  2. 继续比较每一对相邻元素,直到一次遍历完成,这样最大的就在最后面。
  3. 再遍历一次,重复步骤1、2,可以找到把第二个大的值。
  4. 以此类推,继续重复步骤1、2。

代码实现

// objc 版本
- (void)bubbleSort:(int[] )arr withLength:(int )length {
    //总共循环 length 次
    for (int i = 0; i < length - 1; i++) {
        //每一次循环,通过两两比较找出较大的元素,往后移动
        for (int j = 0; j < length - 1 - i; j++) {
            if (arr[j] > arr[j+1]) {
                // 元素交换
                int temp = arr[j+1];
                arr[j+1] = arr[j];
                arr[j] = temp;
            }
        }
    }
}

算法分析

最好时间复杂度:若文件的初始状态是正序的,一趟扫描即可完成排序,时间复杂度是 O(n)
最坏时间复杂度:若初始文件是反序的,比较和移动次数均达到最大值,时间复杂度是 O(n²)
平均事件复杂度:O(n²)
空间复杂度:O(1)
稳定性:稳定。


快速排序

快速排序(QuickSort)是对冒泡排序的一种改进。
核心思想如下:

  1. 挑选基准值(pivot):从数列中挑出一个元素,称为“基准”
  2. 分割(partition):对数列重新排序,所有比基准值小的元素摆放在基准前面,所有比基准值大的元素摆在基准后面(与基准值相等的数可以到任何一边)。在这个分割结束之后,对基准值的排序就已经完成。
  3. 递归子序列,进行分割排序:将小于基准值元素的子序列和大于基准值元素的子序列递归排序

分割的过程有两种实现:

代码实现1

  1. 从左到右扫描一个比基准数大的元素,记 i
  2. 从右到左扫描一个比基准数小的元素,记 j
  3. 交换 ij 指针对应的元素。
  4. 重复操作直到ij相遇,然后将基准元素 list[left] 与左子序列最后的元素 arr[j] 进行交换即可。
  5. 这样就完成一次划分,继续递归对左右两个子序列划分。

代码如下:

/// 快排
void quickSort(int* array, int length, int left, int right) {
    if (left >= right)  return;
    if (right >= length) return;
    if (left < 0) return;
    // 挑选基准值
    int cursor = array[left];
    int i = left;
    int j = right;
    while (true) {
        // 从后面往前找小于 cursor 的元素
        while (j>i && array[j]>=cursor) {
            j--;
        }
        // i、j 相遇
        if (i>=j) break;
        // 从前面往后找大于 cursor 的元素
        while (i<j && array[i]<=cursor) {
            i++;
        }
        // i、j相遇
        if (i>=j) break;
        // 交换 i、j
        int iValue = array[i];
        array[i] = array[j];
        array[j] = iValue;
    }
    // 更新 cursor 位置
    if (i != left) {
        int iValue = array[i];
        array[i] = cursor;
        array[left] = iValue;
    }
    // 继续递归
    if (i-1 > left) {
        quickSort(array, length, left, i-1);
    }
    if (right > j+1) {
        quickSort(array, length, j+1, right);
    }
}

代码实现2

  1. 从右到左扫描一个比基准数小的元素,记 j,移到 i
  2. 从左到右扫描一个比基准数大的元素,记 i,移到 j
  3. 重复操作,直到 ij相遇,一次划分完成,然后把基准数移到 i
  4. 继续递归对左右两个子序列划分。

代码如下:

// objc 版本
- (void)quickSort:(int[] )a withLeft:(int )left withRight:(int )right {
    if (left>=right) {
        return;
    }
    int i,j,cursor;
    i = left;
    j = right;
    cursor = a[i];
    while (true) {
        //从后面往前,找 比基准数小的
        while (j>=0 && a[j]>=cursor && i<j) {
            j--;
        }
        //i、j指针相遇,划分完成
        if (i>=j) {
            break;
        }
        //填坑:右边找到 小于基准数的元素j,将元素j放在i的位置上,默认i指向 是基准数的,且基准数已经备份
        a[i] = a[j];

        //从前面往后,找 比基准数大的
        while (i>=0 && a[i]<=cursor && i<j) {
            i++;
        }
        //i、j指针相遇,完成划分
        if (i>=j) {
            break;
        }
        //填坑:左边找到 大于基准数的元素i,将元素i放在j的位置上,元素j已经空出来了。
        a[j] = a[i];
    }
    //填坑:基准数指向i,元素j已经空出来
    a[i] = cursor;
    //继续递归 子序列,进行划分
    [self quickSort:a withLeft:left withRight:i-1];
    [self quickSort:a withLeft:j+1 withRight:right];
}

算法分析

最好时间复杂度:每次划分过程产生的区间大小都为n/2,时间复杂度是 O(nlogn)
最坏时间复杂度:在每次划分过程产生的两个区间分别包含n-1个元素和1个元素,时间复杂度是 O(n²)
平均时间复杂度:O(nlogn)
空间复杂度:O(1)
稳定性:不稳定。

使用支付宝打赏
使用微信打赏

若你觉得我的文章对你有帮助,欢迎点击上方按钮对我打赏

扫描二维码,分享此文章