Java教程

排序算法:交换排序

本文主要是介绍排序算法:交换排序,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

交换排序的基本思想是:两两比较待排序记录的关键字,一旦发现两个记录不满足次序要求时则进行交换,直到整个序列全部满足要求为止。

1. 冒泡排序

冒泡排序是一种最简单的交换排序算法,通过两两比较相邻记录的关键字,使关键字小的记录如气泡一般逐渐往上“漂浮”(左移),关键字大的记录如石块一样逐渐向下“坠落”(右移)。
冒泡排序过程如图
2

算法描述:

void BubbleSort(SqList &L) {
  m = L.length - 1; 
  flag = 1;  // 用来标记某一趟是否发生交换
  while ((m > 0) && (flag == 1)) {  // 比较多少趟
    flag = 0;  // 如果本趟排序没有发生交换
    for(int i=1; i<=m; i++) {  // 每趟比较多少次
      if (L[i] > L[i+1]) {
        flag = 1;
        int temp = L[i];
        L[i] = L[i+1];
        L[i+1] = temp;
      }
    }
    m--;
  }
}

算法分析:
时间复杂度:\(O(n^2)\)
空间复杂度:\(O(1)\)

算法特点:
(1)稳定排序
(2)可用于链式存储结构
(3)移动次数较多,算法平均时间性能比直接排序差。当初始记录无序,n较大时,此算法不宜采用。

2. 快速排序

冒泡排序一次相邻交换只能消除一个逆序,如果能通过两个(不相邻)的一次交换,消除多个逆序,可大大加快排序速度。
快速排序一次交换可能消除多个逆序。

快速排序算法过程如图:
2
step1:任选一个记录作为枢轴,如选第一个记录,将枢轴记录暂存到r[0],附设low和high指针,初始分别指向下界和上界。
step2:从表最右侧向左搜索,找到第一个小于枢轴pivotkey的记录,将其移到low处。具体操作:当low<high时,若high大于privotkey,左移high,否则high记录放到low处。
step3:从表最左侧向右搜索,找到第一个大于枢轴pivotkey的记录,将其移到high处。具体操作:当low<high时,若low小于privotkey,右移low,否则low记录放到high处。
step4:重复step2和step3直到low=high。此时low或high的位置就是枢轴在此趟排序中的最终结果,原表被分成两个子表。

(思考:枢轴的位置如果任意选,非第一个记录,算法是不是会有所差别?)

算法描述:

void QuickSort(SqList &L) {
  QSort(L, 1, L.length);
}

void QSort(SqList &L, int low, int high) {
  if (low < high) {
    int privotloc = Partition(L, low, high);
    QSort(L, low, privotloc -1);
    QSort(L, privotloc + 1, high);
  }
}

int Partition(SqList &L, int low, int high) {
  L[0] = L[low];  // 用子表的第一个记录做枢轴记录
  while (low < high) {
    while (low < high && high > L[0]) high--;
    L[low] = L[high];
    while (low < high && low < L[0]) low++;
    L[high] = L[low]; 
  }
  L[low] = L[0];
  return low;
}

算法分析:
时间复杂度分析:\(O(nlog_2n)\)
空间复杂度分析:需要一个递归栈,最好\(O(log_2n)\),最坏\(O(n)\)

算法分析:

  1. 非顺次移动导致排序方法不稳定
  2. 需要定位上下界,适合用于顺序结构,很难用于链式结构
  3. n较大时,在平均情况下 快速排序是所有内部排序中最快的一种,所以其适合初始记录无序、n较大时的情况(尤其不适合有序)。
这篇关于排序算法:交换排序的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!