五种经典排序算法

冒泡排序

1. 总体思路
   通过对待排序序列从前向后（从下标较小的元素开始）,依次对相邻两个元素的值进行两两比较，若发现前一个数大于后一个数则交换，使值较大的元素逐渐从前移向后部，就如同水底下的气泡一样逐渐向上冒
   示意图：

   

2. 代码实现

#include<stdio.h>
void Bubble_Sort(int arr[], int n)
{
	for (int i = 0; i < n - 1; i++)//外层循环控制轮数，即遍历数组的次数，每一轮会确定一个最大值放到末尾
	{
		for (int j = 0; j < n - i - 1; j++)//内层循环控制每一轮比较相邻两元素的次数
		{
			if (arr[j] > arr[j + 1])//如果前一个比后一个大，交换
			{
				int temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}
	}
}

int main()
{
	int arr[5];
	int n = sizeof(arr) / sizeof(arr[0]);
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &arr[i]);
	}

	Bubble_Sort(arr, n);

	for (int j = 0; j < n; j++)
	{
		printf("%d ", arr[j]);
	}

	return 0;
}

3. 关键点解释

• 先介绍在这个程序中两个重要的概念：轮数和比较次数。轮数是遍历数组的次数，每一次遍历都会确定一个最大数冒泡到最后；次数是每一轮要比较相邻两两元素多少次
• n代表元素个数
• 在函数Bubble_Sort的嵌套循环中，外层循环控制轮数i，（i = n-1），内层循环控制比较次数j，（j=n-i-1）

插入排序

1. 总体思路
   插入排序的核心思想是将未排序的元素逐个插入已排序部分的合适位置，直到整个数组排序完成
   示意图：

2. 代码实现

#include <stdio.h>
void Insert_Sort(int arr[], int n)
{
    int key,i,j;

    // 将第一个元素视为已排列部分，从第二个元素开始遍历数组，将其插入到已排序部分的合适位置
    for (i = 1; i < n; i++) 
    {
        key = arr[i]; //key是当前要插入的元素
        int j = i - 1;//循环之前，arr[j]是已排序部分的最后一个元素

        while (j >= 0 && arr[j] > key) 
        {
            arr[j + 1] = arr[j]; // 将大于key的元素向后移动
            j--;
        }

        // 循环j结束之后，arr[j]此时刚好是不大于key的数，将key插入到arr[j]之后一个位置即arr[j+1]
        arr[j+1] = key;
    }
}

// 测试插入排序的例子
int main() 
{
    int arr[5];
    int n = sizeof(arr) / sizeof(arr[0]);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &arr[i]);
    }

    Insert_Sort(arr, n);

    for (int i = 0; i < n; i++)
    {
        printf("%d ", arr[i]);
    }

    return 0;
}

3. 关键点解释

• 初始已排序部分：将第一个元素视为已排序部分
• 逐个插入：遍历未排序部分的每个元素，在已排序部分中找到合适的位置并插入
• 重复直到完成：重复以上步骤，直到所有元素都插入到已排序部分

选择排序

1. 总体思路
   选择排序是通过遍历数组，选择出数组的最小值，与指定位置交换数据，遍历完整个数组的所有位置就完成排序
   示意图：

2. 代码实现

#include<stdio.h>
void Select_Sort(int arr[], int n)
{
	int i, j, min_index;//i是未排序部分的第一个元素的索引，j是i之后一个元素的索引，min_index是未排序部分最小元素的索引
	for (i = 0; i < n - 1; i++)//外层循环遍历数组的前n-1个元素
	{
		min_index = i;
		for (j = i + 1; j < n; j++)//内层循环用来遍历未排序部分第一个元素之后的所有元素，找到其中的最小值与未排序部分第一个元素进行交换
		{
			if (arr[min_index] > arr[j])
			{
				min_index = j;
			}
        }
		
		int temp = arr[i];//交换
		arr[i] = arr[min_index];
		arr[min_index] = temp;

	}
}
//主函数测试
int main()
{
	int arr[5];
	int n = sizeof(arr) / sizeof(arr[0]);
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &arr[i]);
	}

	Select_Sort(arr, n);
	for (int j = 0; j < n; j++)
	{
		printf("%d ", arr[j]);
	}

	return 0;

}

3. 关键点解释

• 本方法的核心是每次将数组未排序部分第一个元素之后的若干个数字中的最小值和未排序部分的第一个元素交换
• i是未排序部分第一个元素的索引，j是i后面一个元素的索引，min_index是未排序部分最小元素的索引

快速排序

1. 总体思路

• 概念
  快速排序是一种高效的排序算法，采用分治策略。它的基本思想是：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，然后分别对这两部分记录继续进行排序，以达到整个序列有序

• 总体步骤

  • 选择基准值：从数列中挑出一个元素作为"基准"（一般挑选数组第一个元素或最后一个元素）

  • 分区操作：将数列重新排列，所有比基准值小的元素放在基准前面，所有比基准值大的元素放在基准后面

  • 递归排序：递归地对基准值左右两个子序列进行快速排序
    示意图：

    

2. 代码实现

#include <stdio.h>
// 交换两个元素的值
void Swap(int* a, int* b) 
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

// Hoare法分区函数实现单趟排序
int PartSort(int* arr, int left, int right)
{
    int key = left;     // 使用key保存基准值下标
    while (left < right)
    {
        while (left < right && arr[key] <= arr[right]) 
        {    // 只找小的，等于要过滤，找前判断right有没有走过
            right--;
        }
        
        while (left < right && arr[key] >= arr[left]) 
        {
            left++;
        }
        
        if (left < right)
        {    // 没有相遇时左右交换
            Swap(&arr[left], &arr[right]);
        }
    }
    
     // left和right相遇后交换基准值和相遇位置的值，并返回基准值的下标
    Swap(&arr[key], &arr[left]);  
    return left;
}

// 快速排序递归实现
void QuickSort(int* arr, int begin, int end)
{
    // 当区间不存在或只有一个元素时，不需要排序，直接返回
    if (begin >= end) 
    {
        return;
    }
    
    // 单趟排序，获取基准值位置
    int keyIndex = PartSort(arr, begin, end);
    // 递归排序左半部分 [begin, keyIndex-1]
    QuickSort(arr, begin, keyIndex - 1);
    // 递归排序右半部分 [keyIndex+1, end]
    QuickSort(arr, keyIndex + 1, end);
}

// 测试代码
int main() 
{
    int arr[] = {6, 1, 2, 7, 9, 3, 4, 5, 10, 8};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    printf("排序前: ");
    for (int i = 0; i < n; i++) 
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
    
    QuickSort(arr, 0, n - 1);
    
    printf("排序后: ");
    for (int i = 0; i < n; i++) 
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
    
    return 0;
}

3. 关键点解释

• PartSort函数思路：
  • 初始化：选择arr[left]作为基准值，key记录基准值位置
  • 右指针移动：从右向左扫描，找到第一个小于基准值的元素
  • 左指针移动：从左向右扫描，找到第一个大于基准值的元素
  • 元素交换：交换左右指针所指的元素
  • 重复过程：继续移动指针并交换，直到左右指针相遇
  • 基准归位：将基准值交换到相遇位置
• QuickSort函数思路分析：
  • 分解：通过PartSort将数组分成两个子数组。左子数组：所有元素 ≤ 基准值；右子数组：所有元素 ≥ 基准值
  • 解决：递归地排序两个子数组
    QuickSort(arr, begin, keyIndex - 1)：排序左半部分
    QuickSort(arr, keyIndex + 1, end)：排序右半部分
  • 合并：由于是原地排序，不需要显式合并步骤

归并排序

1. 总体思路
   归并排序采用分治策略：
   分：将数组递归地分成两半，直到每个子数组只有一个元素（这时候认为每一个单元素数组为有序数组）
   治：将两个已排序的子数组合并成一个有序数组，直到所有元素排序完成

一张示意图帮助理解这个过程

2. 代码实现

#include<stdio.h>
#include<stdlib.h>
//merge函数：合并两个有序数组
void merge(int arr[], int left, int mid, int right) 
{
    // left: 左子数组起始索引, mid: 中间点, right: 右子数组结束索引

    int n1 = mid - left + 1;  // 计算左半部分元素个数
    int n2 = right - mid;     // 计算右半部分元素个数

    //边界检查
    if(left > right || mid < left || mid >= right) 
    {
        return;
    }

    // 检查数组大小是否有效
    if (n1 <= 0 || n2 <= 0) 
    {
        return;
    }

    // 创建临时数组存放左右两半的数据
    int* L = (int*)malloc(n1 * sizeof(int));
    int* R = (int*)malloc(n2 * sizeof(int));

    //内存分配检查
    if (L == NULL || R == NULL) 
    {
        if (L) free(L);
        if (R) free(R);
        printf("内存分配失败\n");
        return;
    }

    // 拷贝数据：把原数组分成左右两个临时数组
    for (int i = 0; i < n1; i++)
    {
        L[i] = arr[left + i];// 拷贝左半部分
    }
    for (int j = 0; j < n2; j++)
    {
        R[j] = arr[mid + 1 + j]; // 拷贝右半部分
    }
        
    // 关键步骤：合并两个有序数组
    int i = 0, j = 0, k = left;  // i指向L, j指向R, k指向原数组

    // 比较两个数组的元素，取较小的放入原数组
    while (i < n1 && j < n2) 
    {
        if (L[i] <= R[j]) 
        {      // 稳定排序的关键：相等时取左边的
            arr[k] = L[i];       // 左数组元素较小，放入原数组
            i++;                 // 左数组指针后移
        }
        else 
        {
            arr[k] = R[j];       // 右数组元素较小，放入原数组
            j++;                 // 右数组指针后移
        }
        k++;                     // 原数组指针后移
    }

    // 处理剩余元素：如果左数组还有剩余，全部拷贝过去
    while (i < n1) 
    {
        arr[k] = L[i];
        i++; k++;
    }

    // 处理剩余元素：如果右数组还有剩余，全部拷贝过去
    while (j < n2) 
    {
        arr[k] = R[j];
        j++; k++;
    }

    free(L);  // 释放临时数组内存
    free(R);
}

//mergeSort函数：归并排序主函数
void mergeSort(int arr[], int left, int right)
{
    if (left < right) 
    {  // 递归终止条件：子数组至少要有2个元素

        int mid = left + (right - left) / 2;  // 防止整数溢出的取中方法
        if (mid >= left && mid < right)
        {
            mergeSort(arr, left, mid);      // 递归排序左半部分
            mergeSort(arr, mid + 1, right); // 递归排序右半部分

            merge(arr, left, mid, right);   // 合并两个已排序的部分
        }  
    }
}

//main函数测试
int main()
{
    int arr[] = { 12, 11, 13, 5, 6, 7 };
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("原始数组: ");
    for (int i = 0; i < n; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");

    mergeSort(arr, 0, n - 1);

    printf("归并排序后: ");
    for (int i = 0; i < n; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
    return 0;
}

3. 关键点解释

• 关键思想
  • 分治策略：将大问题分解为小问题解决，再合并结果
  • 递归实现：不断将数组二分，直到单个元素自然有序
• 关键步骤
  分解阶段
  • 计算中间点：mid = left + (right - left) / 2（防溢出）
  • 递归分解左右子数组，直到单个元素
    合并阶段（核心）
  • 创建两个临时数组存放左右子数组
  • 双指针比较：比较两个子数组当前元素，取较小者放入原数组
  • 稳定性保证：L[i] <= R[j]确保相等时左数组元素优先
  • 剩余元素处理
  • 某个子数组有剩余时，直接全部拷贝（因为已有序）
    形象比喻
    就像把一副乱牌分成两半，分别整理好后再像发牌一样合并

总结

1. 冒泡排序： 重复遍历，两两比较，大的下沉。像气泡一样，每一轮将最大的元素“浮”到最终位置
2. 选择排序： 打擂台，选最小，放前面。每一轮从未排序部分中选出最小（或最大）的元素，将其与未排序部分的第一个元素交换
3. 插入排序： 摸牌理牌，逐个插入。像打扑克摸牌一样，将每个新元素插入到前面已经排好序的序列中的正确位置
4. 快速排序： 选定基准，小数左大数右，递归处理。选择一个“基准”元素，将数组分成“小于基准”和“大于基准”的两部分，然后对这两部分递归地进行相同操作
5. 归并排序： 先分后合，有序合并。采用分治法，先将数组递归地分成两半，直到不可再分，然后再将两个有序的子数组合并成一个更大的有序数组