第5章 基础排序

目录5.1排序问题概述5.2冒泡排序5.3选择排序5.4快速排序5.5其它排序算法简介5.1排序算法概述排序是计算机科学中最基础、最常用的算法之一，在我们的日常生活中也无处不在。它不仅是数据处理的基础，也是许多复杂算法的核心组成部分。在本章中，我们将深入学习几种经典的排序算法，包括冒泡排序、选择排序和快速排序。我们将逐一分析它们的基本原理、时间复杂度、空间复杂度以及各自的适用场景，帮助大家建立起对算法效率的直观认识。第5章排序定义：将数据按规则重排。常见算法：冒泡、选择、快速、插入、希尔、归并、堆排序等。比较排序：比大小定次序，下界O(nlogn)。非比较排序：利用数据特性，可达O(n)，需额外空间。稳定性定义：稳定：相等元素相对顺序不变。不稳定：不保证相对顺序。（3）算法稳定性5.1排序问题概述5.2.1冒泡排序原理核心思想：重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。执行过程：每一趟冒泡都会将当前未排序区的最大值“冒泡”到未排序区的末尾。算法特点：n个数据需要进行n-1趟冒泡，每趟比较次数递减。核心代码：通过两层循环实现，外层循环控制趟数，内层循环进行相邻元素的比较与交换。for(inti=0;i<n-1;i++){for(intj=0;j<n-1-i;j++)

{if(a[j]>a[j+1])swap(a[j],a[j+1]);}}算法说明：1.时间复杂度为O(n²)，属于稳定排序算法。2.优化策略：可通过设置标志位，若某一趟未发生交换则说明已有序，提前退出循环。5.2.2冒泡排序程序5.2.3车厢重组（冒泡排序应用）问题描述：通过旋转桥交换相邻车厢，求将车厢按编号排序的最少旋转次数。算法分析：问题本质就是统计冒泡排序过程中发生交换操作的次数。通过引入计数器并利用提前退出机制可优化效率。for(inti=0;i<n-1;i++){boolok=true;for(intj=0;j<n-1-i;j++){if(a[j]>a[j+1]){swap(a[j],a[j+1]);count++;ok=false;}}if(ok)break;//提前退出优化}5.3.1选择排序原理核心思想：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。（1）核心思想排序过程：1.从未排序区找到最小元素。2.将其与未排序区的第一个元素交换。3.缩小未排序区，重复上述步骤。（2）排序过程算法特点：交换次数比冒泡排序少，但无法提前退出，时间复杂度为O(n²)。（3）算法特点5.3.2选择排序程序核心思想：外层循环遍历每个位置，内层循环寻找最小值的下标，最后进行交换。算法特性：时间复杂度为O(n²)，是不稳定排序算法。for(inti=0;i<n-1;i++)

//进行n-1轮选择{intk=i; //最小元素的下标

for(intj=i+1;j<n;j++) //在当前无序区a[i]..a[n-1]中选最小的元素a[k]

if(a[j]<a[k])k=j;if(k!=i)swap(a[i],a[k]); //交换a[i]和a[k]，将当前最小值放到a[i]位置}5.4.1快速排序原理核心思想：采用分治思想。选择一个基准值，将数据分为两部分，左边小于基准值，右边大于基准值，然后递归处理两部分。执行过程：1.选择基准值；2.分区操作（小左大右）；3.递归排序左右子数组。算法特点：平均时间复杂度为O(nlogn)，最坏情况O(n²)，属于不稳定排序。图5-8快速排序分区与归位过程示意图核心代码（递归实现）：voidquick_sort(inta[],intleft,intright){if(left>=right)return;intL=left,R=right,key=a[L];while(L<R)

{while(L<R&&a[R]>=key)R--;while(L<R&&a[L]<=key)L++;if(L<R)swap(a[L],a[R]);}swap(a[left],a[L]);quick_sort(a,left,L-1);quick_sort(a,R+1,right);}5.4.2快速排序程序问题描述：找出数列排序后的第k小的数。算法分析：利用快速排序的分区思想，只需递归处理第k个数所在的子数组，无需完全排序。核心优化：在递归前判断第k个数是否在当前区间内，不在则直接返回，避免无效递归。5.4.3第k小整数（快速排序应用）if(left>k||right<k)return;//关键优化：提前终止5.5.1插入排序简介核心思想：将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据。核心思想生活类比：如同打牌时抓牌，每抓一张就插入到手中合适的位置，保持手牌有序。生活类比算法特点：简单直观，对基本有序的数据效率较高；时间复杂度O(n²)，属于稳定排序算法。算法特点排序算法对比算法平均时间复杂度最坏时间复杂度空间复杂度稳定性冒泡排序O(n²)O(n²)O(1)稳定选择排序O(n²)O(n²)O(1)不稳定快速排序O(nlogn)O(n²)O(logn)不稳定插入排序O(n²)O(n²)O(1)稳定冒泡排序：相