• 数据结构与算法基础-学习-31-交换排序之冒泡排序、快速排序

    目录

    一、交换排序基本思想

    二、冒泡排序基本思想

    三、冒泡排序算法实现思路

    1、第一趟

    2、第二趟

    3、第三趟

    4、第四趟

    5、第五趟

    四、冒泡排序算法源码

    1、BubbleSortSentrySqQueue

    五、冒泡排序算法效率

    六、冒泡排序Linux环境编译测试

    七、快速排序基本思想

    八、快速排序算法实现思路

    1、第一趟

    2、第二趟

    九、快速排序算法源码

    1、QuickSortPartionSentrySqQueue

    2、QuickSortRecurtionSentrySqQueue

    十、快速排序算法效率

    十一、快速排序Linux环境编译测试

    排序的其他相关知识点和源码分享可以参考之前的博客：   

    《数据结构与算法基础-学习-30-插入排序之直接插入排序、二分插入排序、希尔排序》

    一、交换排序基本思想

    两两比较，如果发生逆序则交换位置，直到所有数据记录都排好序为止。

    二、冒泡排序基本思想

    每趟不断地将数据记录两两比较，并按照升序或降序规则进行交换。

    三、冒泡排序算法实现思路

    这里的哨兵起的是临时变量的作用，在交换元素时使用。

    我们还是以升序为例。

    1、第一趟

    一共有7个元素，需要比较6次，因为没有8号位。

    （1）1小于2，不要交换，继续

    （2）2小于8，不要交换，继续

    （3）8大于5，需要交换，继续

    （4）8大于4，需要交换，继续

    （5）8大于6，需要交换，继续

    （6）8大于3，需要交换，6次比较完，已经把最大值8放到了最后一位，那下一趟比较时，就不需要比较8了。

    2、第二趟

    一共有6个元素需要比较，总共需要比较5次，因为7号位的8已经完成排序。

    （1）1小于2，不要交换，继续

    （2）2小于5，不要交换，继续

    （3）5大于4，需要交换，继续

    （4）5小于6，不要需要交换，继续

    （5）6大于3，需要交换，5次比较完，已经把最大值6放到了最后一位，那下一趟比较时，就不需要比较6，8了。

    3、第三趟

    一共有5个元素需要比较，总共需要比较4次，因为6和8已经完成排序。

    规律都知道了，我们这就快进一些，跳过了一些对比步骤。

    1，2，3，4，5都是升序不需要移动。

    （1）5大于3，需要交换，4次比较完，已经把最大值5放到了最后一位，那下一趟比较时，就不需要比较5，6，8了。

    4、第四趟

    一共有4个元素需要比较，总共需要比较4次，因为5，6和8已经完成排序。

    规律都知道了，我们这就快进一些，跳过了一些对比步骤。

    1，2，4都是升序不需要移动。

    （1）4大于3，需要交换，3次比较完，已经把最大值4放到了最后一位，那下一趟比较时，就不需要比较4，5，6，8了。

    5、第五趟

    一共有4个元素需要比较，总共需要比较3次，因为4，5，6和8已经完成排序。

    1，2，3，4就是升序的，没有交换元素，说明序列已经是有序的，排序完成。

    四、冒泡排序算法源码

    1、BubbleSortSentrySqQueue

    1. Status BubbleSortSentrySqQueue(SqQueue* Queue)
    2. {
    3.     JudgeAllNullPointer(Queue);
    4.  
    5.     if (Queue->Flag != INT_TYPE_FLAG)
    6.     {
    7.         return FailFlag;
    8.     }
    9.  
    10.     int*         Array    = (int*)(Queue->Data);
    11.     int          SwapFlag = 0;
    12.     QueueLenType i;
    13.     QueueLenType j;
    14.  
    15.     for (i = 1; i < Queue->SqQueueLen - 1; i++)//长度n，比较（n - 1）趟。
    16.     {
    17.         SwapFlag = 0;
    18.         for (j = 1; j < Queue->SqQueueLen - i; j++)//每趟，比较 （n - 第i趟） 次。找个测试数据更明显，好理解
    19.         {
    20.             if (Array[j] > Array[j + 1])
    21.             {
    22.                 Array[0]     = Array[j + 1];
    23.                 Array[j + 1] = Array[j];
    24.                 Array[j]     = Array[0];
    25.                 SwapFlag     = 1;
    26.             }
    27.         }
    28.         if (SwapFlag == 0)//如果某一趟不需要进行交换，说明所有元素都是有序的，退出循环。
    29.         {
    30.             break;
    31.         }
    32.     }
    33.     
    34.     LogFormat(Debug,"Bubble Sort SqQueue OK.\n");
    35.  
    36.     return SuccessFlag;
    37. }

    五、冒泡排序算法效率

    情况时间复杂度是否稳定
    最好O(n)稳定
    最坏O(n^2)
    平均O(n^2)

    最好的情况例如冒泡升序排序，数据是升序排列的，只需要比较n-1次即可，不需要移动元素。

    最坏的情况例如冒泡升序排序，数据是降序排列的，

    （1）需要比较次数为：

    长度为n的序列，需要比较n-1次，每次少比一次，直到1为止，可以使用等差求和公式:

    ((n - 1) + 1) * (n - 1) / 2 = （n^2 - n）/ 2

    （2）需要移动次数为：

    每比较一次，需要交换一次，交换需要临时变量存放，一共需要三步，所以乘以3。

    1.                 Array[0]     = Array[j + 1];
    2.                 Array[j + 1] = Array[j];
    3.                 Array[j]     = Array[0];

    （n^2 - n）/ 2 * 3。

    六、冒泡排序Linux环境编译测试

    1. [gbase@czg2 Sort]$ time ./TestSort 
    2. 2023-9-1--[ Debug ]--Init SqQueue OK
    3. 2023-9-1--[ Debug ]--Enter SqQueue OK
    4. 2023-9-1--[ Debug ]--Enter SqQueue OK
    5. 2023-9-1--[ Debug ]--Enter SqQueue OK
    6. 2023-9-1--[ Debug ]--Enter SqQueue OK
    7. 2023-9-1--[ Debug ]--Enter SqQueue OK
    8. 2023-9-1--[ Debug ]--Enter SqQueue OK
    9. 2023-9-1--[ Debug ]--Enter SqQueue OK
    10. 2023-9-1--[ Debug ]--Enter SqQueue OK
    11. 2023-9-1--[ Debug ]--Enter SqQueue OK
    12. 2023-9-1--[ Debug ]--Enter SqQueue OK
    13. 2023-9-1--[ Debug ]--Enter SqQueue OK
    14. 2023-9-1--[ Debug ]--SqQueue Data   :
    15. Data           : [ 0 ,10 ,9 ,8 ,7 ,6 ,5 ,4 ,3 ,2 ,1 ]
    16. FrontIndex     : 0
    17. RearIndex      : 0
    18. SqQueueLen     : 11
    19. SqQueueMaxLen  : 11
    20. Flag           : INT_TYPE_FLAG
    21. 2023-9-1--[ Debug ]--Bubble Sort SqQueue OK.
    22. 2023-9-1--[ Info  ]--Sort Function Elapsed Time   : 0 s
    23. 2023-9-1--[ Info  ]--SqQueue Data   :
    24. Data           : [ 1 ,1 ,2 ,3 ,4 ,5 ,6 ,7 ,8 ,9 ,10 ]
    25. FrontIndex     : 0
    26. RearIndex      : 0
    27. SqQueueLen     : 11
    28. SqQueueMaxLen  : 11
    29. Flag           : INT_TYPE_FLAG
    30. 2023-9-1--[ Debug ]--Destroy SqQueue OK
    31.  
    32. real    0m0.002s
    33. user    0m0.000s
    34. sys     0m0.002s

    七、快速排序基本思想

    快速排序是改进的交换排序。

    1、任取一个元素为中心（一般是第一个元素）。

    2、所有比它小的元素一律前放，比它大的元素一律后放，形成左右两个子表。

    3、对各子表重新选择中心元素并依照上述规则调整。

    4、直到每个子表的元素只剩下一个。

    八、快速排序算法实现思路

    这里的哨兵位也是起到存放临时变量的作用的。

    1、第一趟

    1号位的3作为中间点，存放在哨兵位0中，那Low位置的元素就是空的了。

    哨兵位的3和High的1进行比较，3大于1，将High的1填写到Low上，那样High的位置就空出来了。我们开始从Low找。

    哨兵位的3和Low的1进行比较，3大于1，在3的左边，不需要移动，Low向右移动。

    哨兵位的3和Low的2进行比较，3大于2，在3的左边，不需要移动，Low向右移动。

    哨兵位的3和Low的8进行比较，8大于3，在3的右边，需要移动把Low的8移动到High的位置，Low的位置空了，开始High位置和哨兵进行比较，是不是发现了什么，左边有空位了，就去右边找，找，右边空了，就去左边找，很有规律性。

    哨兵位的3和High的8进行比较，8大于3，在3的右边，不需要移动，High向左移动。

    哨兵位的3和High的6进行比较，6大于3，在3的右边，不需要移动，High向左移动。

    哨兵位的3和High的4进行比较，4大于3，在3的右边，不需要移动，High向左移动。

    Low和High重合，说明Low左边的都比3小，右边的都比3大，把3填到Low的位置。

    Low左边已经排好序了，我们开始排序右边的这些元素。

    2、第二趟

    还是以第一个Low的位置为中心点，这样Low的位置就空出来了，哨兵和HIgh为的5进行比较，发现比8小，HIgh左移。

    哨兵位的5和High的6进行比较，6大于5，在5的右边，不需要移动，High向左移动。

    哨兵位的5和High的4进行比较，5大于4，在5的左边，Low填上4，那High的位置就空出来了，我们开始移动Low。

    哨兵位的5和Low的4进行比较，5大于4，在3的左边，不需要移动，Low向右移动。

    发现Low和High重合，将哨兵填写到Low上，这一段有序了，整个序列就完成了排序。

    九、快速排序算法源码

    1、QuickSortPartionSentrySqQueue

    将Low到High之间元素根据Low为中间值进行分区，返回中间值的最终索引位置。

    1. //返回中间点索引。
    2. QueueLenType QuickSortPartionSentrySqQueue(SqQueue* Queue, QueueLenType Low, QueueLenType High)
    3. {
    4.     JudgeAllNullPointer(Queue);
    5.     
    6.     int* Array = (int*)(Queue->Data);
    7.     Array[0]   = Array[Low];
    8.  
    9.     while (Low < High)
    10.     {
    11.         while (Low < High && Array[0] <= Array[High])//大于等于中间点的值放右边。
    12.         {
    13.             High--;
    14.         }
    15.         Array[Low] = Array[High];
    16.         while (Low < High && Array[0] > Array[Low])//小于中间点的值放左边。
    17.         {
    18.             Low++;
    19.         }
    20.         Array[High] = Array[Low];
    21.     }
    22.     Array[Low] = Array[0];
    23.  
    24.     return Low;
    25. }

    2、QuickSortRecurtionSentrySqQueue

    1. void QuickSortRecurtionSentrySqQueue(SqQueue* Queue, QueueLenType Low, QueueLenType High)
    2. {
    3.     JudgeAllNullPointer(Queue);
    4.  
    5.     if (Low >= High)//退出条件，High必须要大于low。
    6.     {
    7.         return;
    8.     }
    9.     QueueLenType PivotIndex = QuickSortPartionSentrySqQueue(Queue, Low, High);
    10.  
    11.     QuickSortRecurtionSentrySqQueue(Queue, Low, PivotIndex - 1);
    12.     QuickSortRecurtionSentrySqQueue(Queue, PivotIndex + 1, High);
    13. }

    十、快速排序算法效率

    情况时间复杂度是否稳定
    最好O(n * log2^n)不稳定
    最坏O(n^2)
    平均O(n * log2^n)

    1、快速排序不是原地排序，因为递归方法使用了系统栈，不用递归，需要用用户栈实现。

    2、快速排序不适用于对原本有序或基本有序的记录序列进行排序。

    3、划分元素的选取是影响时间性能的关键。

    4、输入数据次序越乱，所选划分值随机性越好，排序速度越快，快速排序不是自然排序方法。

    5、升序快速排序算法使用在倒序排序序列上，会触发最坏的情况，使算法退化为冒泡排序。

    十一、快速排序Linux环境编译测试

    1. [gbase@czg2 Sort]$ time ./TestSort 
    2. 2023-9-1--[ Debug ]--Init SqQueue OK
    3. 2023-9-1--[ Debug ]--Enter SqQueue OK
    4. 2023-9-1--[ Debug ]--Enter SqQueue OK
    5. 2023-9-1--[ Debug ]--Enter SqQueue OK
    6. 2023-9-1--[ Debug ]--Enter SqQueue OK
    7. 2023-9-1--[ Debug ]--Enter SqQueue OK
    8. 2023-9-1--[ Debug ]--Enter SqQueue OK
    9. 2023-9-1--[ Debug ]--Enter SqQueue OK
    10. 2023-9-1--[ Debug ]--Enter SqQueue OK
    11. 2023-9-1--[ Debug ]--Enter SqQueue OK
    12. 2023-9-1--[ Debug ]--Enter SqQueue OK
    13. 2023-9-1--[ Debug ]--Enter SqQueue OK
    14. 2023-9-1--[ Debug ]--SqQueue Data   :
    15. Data           : [ 0 ,10 ,9 ,8 ,7 ,6 ,5 ,4 ,3 ,2 ,1 ]
    16. FrontIndex     : 0
    17. RearIndex      : 0
    18. SqQueueLen     : 11
    19. SqQueueMaxLen  : 11
    20. Flag           : INT_TYPE_FLAG
    21. 2023-9-1--[ Debug ]--Quick Sort Sentry SqQueue OK.
    22. 2023-9-1--[ Info  ]--Sort Function Elapsed Time   : 0 s
    23. 2023-9-1--[ Info  ]--SqQueue Data   :
    24. Data           : [ 4 ,0 ,1 ,2 ,3 ,4 ,5 ,6 ,7 ,8 ,9 ]
    25. FrontIndex     : 0
    26. RearIndex      : 0
    27. SqQueueLen     : 11
    28. SqQueueMaxLen  : 11
    29. Flag           : INT_TYPE_FLAG
    30. 2023-9-1--[ Debug ]--Destroy SqQueue OK
    31.  
    32. real    0m0.002s
    33. user    0m0.000s
    34. sys     0m0.002s
  • 相关阅读:
    Android AndroidStudro版本gradle版本对应
    gltf和glb格式模型用什么软件处理
    我的创作纪念日
    vim 窗口管理
    每周一算法：最短路计数
    DotNet Dictionary 实现简介
    ThreadPoolExecutor 源码分析
    真的卷不动了...
    【安全框架】快速了解安全框架
    返回多维数组转换为一维后的数组：array.flatten()
  • 原文地址：https://blog.csdn.net/qq_45111959/article/details/132618051