交换排序

2022.10.21

冒泡排序


void BubbleSort(ElemType A[], int n){
  bool flag;
  for(int i=0;i<n-1;i++){// 每一趟排序
    flag=false;
    for(int j=n-1;j>i;j--)
      if(A[j-1]>A[j]){
        swap(A[j-1],A[j]);
        flag = true;
      }
    if(flag==false) return; // 本躺遍历后没有发生交换，表已有序
  }
}

空间复杂度：O(1)

时间复杂度：平均O(n^2)，最坏O(n^2)

快速排序

快速排序可视化展示


#include "stdio.h"

int Partition(SqList &L, int low, int high){
    // 将第一个元素设为轴
    DataType mid_e=GetItemRe(L,low);
    // 寻找轴
    while(low<high){
        printf("[%d - %d : %d] ",low,high, ele_get_weight(mid_e));
        ListPrint(L);
        while(low<high&& !ele_small(GetItemRe(L,high),mid_e))high--;
        ListSet(L,low,GetItemRe(L,high));
        printf("[%d - %d : %d] ",low,high, ele_get_weight(mid_e));
        ListPrint(L);
        while(low<high&& !ele_big(GetItemRe(L,low),mid_e))low++;
        ListSet(L,high,GetItemRe(L,low));
    }
    ListSet(L,low,mid_e);
    printf("----------->");ListPrint(L);
    return low;
}

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

void init_test_quick_sort(SqList &L, int num[],int  n){
    for(int i=0;i<n;i++)
        ListInsertIndex(L,i+1,ele_build(num[i]));
}

void test_quick_sort(){
    printf("交换排序 - 快速排序\n");

    SqList L;
    ListInit(L);
    int num[] = {5,3,1,7,2,4,6,8};
    init_test_quick_sort(L,num,8);
    quick_sort(L);
}

运行结果：
交换排序 - 快速排序
[1 - 8 : 5]  5  3  1  7  2  4  6  8 
[1 - 6 : 5]  4  3  1  7  2  4  6  8 
[4 - 6 : 5]  4  3  1  7  2  7  6  8 
[4 - 5 : 5]  4  3  1  2  2  7  6  8 
-----------> 4  3  1  2  5  7  6  8 
[1 - 4 : 4]  4  3  1  2  5  7  6  8 
[1 - 4 : 4]  2  3  1  2  5  7  6  8 
-----------> 2  3  1  4  5  7  6  8 
[1 - 3 : 2]  2  3  1  4  5  7  6  8 
[1 - 3 : 2]  1  3  1  4  5  7  6  8 
[2 - 3 : 2]  1  3  3  4  5  7  6  8 
[2 - 2 : 2]  1  3  3  4  5  7  6  8 
-----------> 1  2  3  4  5  7  6  8 
[6 - 8 : 7]  1  2  3  4  5  7  6  8 
[6 - 7 : 7]  1  2  3  4  5  6  6  8 
-----------> 1  2  3  4  5  6  7  8

$nlog_2n$ )，是所有算法中平均性能最优的排序算法

例题

对n个不同的元素利用冒泡法从小到大排序，在（）情况下元素交换的次数最多。 A. 从大到小排列好的 B. 从小到大排列好的 C. 元素无序 D. 元素基本有序
【答案】：A
若用冒泡排序算法对序列(10,14,26,29,41,52)从大到小排序，则需进行（）次比较。 A. 3 B. 10 C. 15 D. 25
【答案】：C
[10],14,26,29,41,52
14,26,29,41,52,[10] - 5
26,29,41,52,[14],[10] - 5+4
5+4+3+2+1=6*5/2=15
用某种排序方法对线性表 {25,84,21,47,15,27,68,35,20} 进行排序时，元素序列的变化情况如下： 1)25, 84, 21, 47, 15, 27, 68, 35, 20 2)20, 15, 21, 25, 47, 27, 68, 35, 84 3)15, 20, 21, 25, 35, 27, 47, 68, 84 4)15, 20, 21, 25, 27, 35, 47, 68, 84 则所采用的排序方法是（）。 A. 选择排序 B. 插入排序 C. 2路归并排序 D. 快速排序
【答案】：D
一组记录的关键码为(46,79,56,38,40,84)，则利用快速排序的方法，以第一个记录为基准，从小到大得到的一次划分结果为( ）。 A. (38, 40, 46, 56, 79, 84) B. (40, 38, 46, 79, 56, 84) C. (40, 38, 46, 56, 79, 84) D. (40, 38, 46, 84, 56, 79)
【答案】：C

快速排序算法在（）情况下最不利于发挥其长处 A. 要排序的数据量太大 B.要排序的数据中含有多个相同值 C．要排序的数据个数为奇数 D.要排序的数据已基本有序
【答案】：D
就平均性能而言，目前最好的内部排序方法是（）。 A.冒泡排序 B.直接插入排序 C.希尔排序 D.快速排序
【答案】：D
数据序列F={2,1,4,9,8,10,6,20}只能是下列排序算法中的(）两趟排序后的结果。 A. 快速排序 B. 冒泡排序 C. 选择排序 D. 插入排序
【答案】：A
对数据序列{8,9,10,4,5,6,20,1,2}采用冒泡排序（从后向前次序进行，要求升序），需要进行的趟数至少是（）. A. 3 B. 4 C. 5 D. 8
【答案】：C
1 {[4,8,9,10],5,6,20,1,2}
2 {[4,5,8,9,10],6,20,1,2}
3 {[4,5,6,8,9,10],20,1,2}
4 {[1,4,5,6,8,9,10,20],2}
5 {[1,2,4,5,6,8,9,10,20]}
对下列关键字序列用快排进行排序时，速度最快的情形是（），速度最慢的情形是( ）. A. {21, 25, 5, 17, 9, 23, 30} B. {25, 23, 30, 17, 21, 5, 9} C. {21, 9, 17, 30, 25, 23, 5} D. {5, 9, 17, 21, 23, 25, 30}
【答案】：A,D，排好序的表快排最慢！
对下列 4个序列，以第一个关键宇为基准用快速排序算法进行排序，在第一趟过程中移动记录次数最多的是() A. 92, 96, 88, 42, 30, 35, 110, 100 B. 92, 96, 100, 110, 42, 35, 30, 88 C. 100, 96, 92, 35, 30, 110, 88, 42 D. 42, 30, 35, 92, 100, 96, 88, 110
【答案】：B
A [35, 30, 88, 42, 92, 96, 110, 100] 3
B [88, 30, 35, 42, 92, 110, 100, 96] 7
下列序列中，( ）可能是执行第一趟快速排序后所得到的序列。 I. {68, 11, 18, 69, 23, 93, 73} II. {68,11,69,23,18,93,73} III. (93, 73, 68, 11, 69, 23, 18} IV. {68, 11, 69, 23, 18, 73, 93} A. I. IV B. II. III C. III, IV D. 只有IV
【答案】：C
对n个关键宇进行快速排序，最大递归深度为（），最小递归深度为（） A. 1 B. n C. log2 n D. nlog2 n
【答案】：B,C
【2010 统考真题】对一组数据(2,12,16,88,5,10)进行排序，若前了趟排序结果如下：第一趟排序结果：2,12,16,5,10,88 第二趟排序结果：2,12,5,10,16,88 第三趙排序结果：2,5,10,12,16,88 则采用的排序方法可能是（）。 A. 冒泡排序 B. 希尔排序 C. 归并排序 D. 基数排序
【答案】：A
【2010 统考真题】采用递归方式对顺序表进行快速排序。下列关于递归次数的叙迷中正确的是（） A. 递归次数与初始数据的排列次序无关 B. 每次划分后，先处理较长的分区可以減少递归次数 C. 每次划分后，先处理较短的分区可以減少递归次数 D. 递归次数与每次划分后得到的分区的处理顺序无关
【答案】：D
【2011 统考真题】为实现快速排序算法，待排序序列宜采用的存储方式是（)。 A. 顺序存储 B. 敞列存储 C. 链式存储 D. 索引存僗
【答案】：A
【2014 统考其题】下列选项中，不可能是快速排序第2趟排序结果的是（）. A. 2, 3, 5, 4, 6, 7, 9 B. 2, 7, 5, 6, 4, 3,9 C. 3, 2, 5, 4, 7, 6,9 D. 4.2,3,5,7,6,9
【答案】：C
【2019 统考真题】排序过程中，对尚未确定最终位罗的所有元素进行一遍处理称为一“趟”。下列序列中，不可能是快速排序第二趟结果的是()
A. 5, 2, 16, 12, 28, 60, 32, 72 C. 2, 12, 16, 5, 28, 32, 72, 60 B. 2, 16, 5, 28, 12, 60, 32, 72 D. 5, 2, 12, 28, 16, 32, 72, 60
【答案】：D