重点算法排序之快速排序、归并排序（上篇）

news/2024/11/7 12:43:07/

文章目录

一、排序的概念及常见的排序算法

二、快速排序的思想及代码详解

2、1 快速排序的思想 

2、2 挖坑法

2、2、1 挖坑法实现思想

2、2、2 挖坑法举例

2、2、3 挖坑法代码实现

2、3 左右指针法

2、3、1 左右指针法实现思想

2、3、2 左右指针法举例

2、3、3  左右指针法代码实现

2、4 前后指针法

2、4、1 前后指针发实现思想

2、4、2  前后指针法举例

2、4、3 前后指针代码实现

三、归并排序的思想及代码详解

3、1 归并排序的思想实现

3、2 归并排序的代码实现

总结

标题：重点算法排序之快速排序、归并排序（上篇）

作者：@Ggggggtm

寄语：与其忙着诉苦，不如低头赶路，奋路前行，终将遇到一番好风景

 

一、排序的概念及常见的排序算法

  排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。

  在排序中我们还经常讨论这个排序是否稳定？那到底怎么来判断一个潘旭是否稳定呢？我们先看一下排序稳定的概念。

  稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

   我们比较常见的排序有六种：插入排序、希尔排序、选择排序、堆排序、快速排序、归并排序。应用较多的，也是相对来说比较重要的有快速排序和归并排序。我们本篇文章先来详细介绍一下快速排序和归并排序的思想及代码详解，下篇文章会写出插入排序、希尔排序、选择排序、堆排序的思想及代码详解。

二、快速排序的思想及代码详解

2、1 快速排序的思想 

 任取待排序元素序列中的某元素作为基准值（我们这里一般选择数组的第一个元素或者最后一个元素或者中间的元素），将数组的元素与基准值比较分成左、右子序列，左子序列中所有元素均小于或等于基准值，右子序列中所有元素均大于或等于基准值，然后对左右子序列重复该过程（递归实现排序），直到所有元素都排列在相应位置上为止。 

  我们举一个例子一起理解一下。加入我们给出如下数组： 

int arr[]={49,38,65,97,76,13,27,49};

  对上面的数组进行快排，我们按照快排的思想分为三步骤进行排序，如下：

  1. 我们先选出基准值，我们在这里选择数组的最左边的数。
  2. 按照基准直对数组进行初次排序，分成左、右子序列。左子序列中所有元素均小于或等于基准值，右子序列中所有元素均大于或等于基准值。
  3. 递归排序左右子序列，当子序列中只有一个元素时我们就不在递归（递归的停止条件）。

   当递归结束时，此时的序列已经为有序的了。我们不难发现，快速排序递归实现有序是用了分治的思想。我们刚开始是把一个无序的数组分成了左、右子序列数组，进而分别对左、右子序列再分，直到分成左、右子序列只有一个数据时（我们可以把一个数据看成有序的），就不会再分。这时递归结束后就已经是有序的了。 

   那么具体显现的思路有几种呢？在这里我给出三种是实现方法：挖坑法、左右指针法、前后指针法。

2、2 挖坑法

2、2、1 挖坑法实现思想

  我们先来了解一下挖坑法的主要思想：

  1. 先选出一个坑的位置（基准值），我们选择坑的位置一般会选最左边或者最右边。
  2. 第一次排序：当我们选择坑的位置为最左边时，我们再从数组的最右边依次往前找找比基准直小的数放到坑的位置。更新坑的位置为从右边找到比基准直小的位置。我们再从左边依次找比基准直大的数字放到新坑的位置。反复此操作，当左右相遇时（此时该地方为坑），把基准值放到坑里就行。
  3. 递归重复第二步骤的操作达到有序。

2、2、2 挖坑法举例

  通过上述思想我们举一个例子具体看一下怎么实现的。我们给出如下数组：

   我们按照上述挖坑法思想来看一下具体实现：

  1. 选出坑的位置（基准直）；
  2. 第一次排序；
  3. 递归排序左、右子序列。

2、2、3 挖坑法代码实现

void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}
void QuickSort(int arr[], int left, int right)
{if (left >= right){return;}int index = GetMid(arr, left, right);Swap(&arr[left], &arr[index]);int begin = left;int end = right;int pivot = begin;int key = arr[begin];while (begin < end){while (begin<end && arr[end] >= key){end--;}arr[pivot] = arr[end];pivot = end;while (begin < end && arr[begin] <= key){begin++;}arr[pivot] = arr[begin];pivot = begin;}arr[begin] = key;QuickSort(arr, left, begin - 1);QuickSort(arr, begin + 1, right);
}
void Print(int arr[], int n)
{int i = 0;for (i = 0; i < n; i++){printf("%d ", arr[i]);}
}
void TestSort()
{int arr[10] = { 0,9,8,7,6,5,4,3,2,1 };int n = 10;QuickSort(arr, 0, n - 1);Print(arr, n);
}
int main()
{TestSort();return 0;
}

2、3 左右指针法

2、3、1 左右指针法实现思想

  我们先来了解一下左右指针法的主要思想：

  1. 先选出一个基准值，我们选择坑的位置一般会选最左边或者最右边或者中间的数据。
  2. 第一次排序：我们定义两个指针。初始时，一个指针（begin指针）指向最左边的数据，另一个指针（end指针）指向最后一个数据。begin指针向右找比基准值大的数据，找到了就停下来。end指针向左找比基准值小的数据，找到了就停下来。然后交换两个指针的指向的数据，直到begin指针与end指针相遇，最后把基准值与begin与end相遇位置的数据交换即可。
  3. 递归左右子区重复第二步骤的操作达到有序。

2、3、2 左右指针法举例

  同样，我们先给出一个数组，如下：

  我们用上述的左右指针法的思想来实现一下：

  1. 选出一个基准直（数组最左边的值）；
  2. 定义左右指针，依次往中间找；
  3. 递归左右子区间重复第二步骤达到有序。

2、3、3  左右指针法代码实现

#include<stdio.h>
void Print(int arr[], int n)
{int i = 0;for (i = 0; i < n; i++){printf("%d ", arr[i]);}
}
void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}
void QuickSort(int arr[], int left, int right)
{if (left >= right)return;int begin = left;int end = right;int keyi = begin;while (begin < end){while (begin < end && arr[end] >= arr[keyi]){end--;}while (begin < end && arr[begin] <= arr[keyi]){begin++;}Swap(&arr[begin], &arr[end]);}Swap(&arr[begin], &arr[keyi]);QuickSort(arr, left, begin - 1);QuickSort(arr, begin + 1, right);
}
void TestSort()
{int arr[] = { 3,5,1,2,7,6,4,5,8,0,9,-1 };int n = 12;QuickSort(arr, 0, n - 1);Print(arr,n);
}
int main()
{TestSort();return 0;
}

2、4 前后指针法

2、4、1 前后指针发实现思想

  我们先来了解一下前后指针法的主要思想：

  1. 先选出一个基准值，我们一般只会选择第一个数据作为基准值；
  2. 第一次排序：我们定义两个指针（前后指针）。初始时，前指针（prev指针）指向最左边的数据，后指针（cur指针）指向第二个数据。cur指针向右找比基准值小的数据，找到了就停下来。然后perv指针加一，cur指针与prev指针指向的数据交换。直到cur指针找到最右边停止。最后再把基准值与prev数据交换一下即可。
  3. 递归左右子区重复第二步骤的操作达到有序。

2、4、2  前后指针法举例

 老样子，我们先给出一个数组，如下：

  我们用上述的前后指针法的思想来实现一下：

  1. 先选出一个基准值；
  2. 定义前后指针，进行第一次排序；
  3. 递归实现左右子序列。

2、4、3 前后指针代码实现

#include<stdio.h>
void Print(int arr[], int n)
{int i = 0;for (i = 0; i < n; i++){printf("%d ", arr[i]);}
}
void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}
void QuickSort(int arr[], int left, int right)
{int keyi = left;int prev = left;int cur = left + 1;while (cur <= right){while (arr[cur] < arr[keyi] && ++prev != cur){Swap(&arr[cur], &arr[prev]);}cur++;}Swap(&arr[keyi], &arr[prev]);QuickSort(arr, left, prev - 1);QuickSort(arr, prev + 1, right);
}
void TestSort()
{int arr[] = { 3,5,1,2,7,6,4,5,8,0,9,-1 };int n = 12;QuickSort(arr, 0, n - 1);Print(arr,n);
}
int main()
{TestSort();return 0;
}

  以上就是快速排序的三种不同的实现方法，但是实现的基本思想是大同小异的。接下来我们看一下归并排序。

三、归并排序的思想及代码详解

  归并排序的思想与快速排序的思想有一点相似之处，但又有些不同。当我们理解了快速排序后，归并排序理解起来也就是跟简单了。我们来看一下归并排序的思想实现。

3、1 归并排序的思想实现

  归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

  我们同样将归并排序分为三大步骤：

  1.  找出数组个数的中间值，将数组非为左右子区间；
  2. 递归找到最小的左右区间；
  3. 依次将最小的左右（有序）区间进行归并操作得到有序数组。

  我们结合下面的举例图片更容易理解。

3、2 归并排序的代码实现

void MergeSort(int arr[], int left, int right,int tmp[])
{if (left >= right)return;int mid = left + right >> 1;MergeSort(arr, left, mid, tmp);MergeSort(arr, mid + 1, right, tmp);int begin1 = left;int end1 = mid;int begin2 = mid + 1;int end2 = right;int index = left;while (begin1 <= end1 && begin2 <= end2){if (arr[begin1] < arr[begin2])tmp[index++] = arr[begin1++];elsetmp[index++] = arr[begin2++];}while (begin1 <= end1){tmp[index++] = arr[begin1++];}while (begin2 <= end2){tmp[index++] = arr[begin2++];}for (int i = left; i <= right; i++){arr[i] = tmp[i];}
}
void TestSort()
{int arr[] = { 3,5,1,2,7,6,4,5,8,0,9,-1 };int n = 12;int tmp[12];QuickSort(arr, 0, n - 1，tmp);Print(arr,n);
}
int main()
{TestSort();return 0;
}

总结

   通过上面的学习，我们发现快速排序和归并排序都用了分治的思想来实现的。分支的思想就是把一个复杂的问题分解成很多相对较容易的问题，通过实现相对较容易的小问题后，一步一步返回完成复杂的大问题。 分支的思想在快速排序和归并排序中就得到了很好的体现。快速排序和归并排序在排序中相对来说是十分重要的，我们应该反复练习，达到熟能生巧的地步。

  快速排序和归并排序就讲到这里，希望本篇文章对你有所帮助，后续会持续更新插入排序、希尔排序、选择排序、堆排序的详解。

  感谢阅读ovo~


http://www.ppmy.cn/news/9111.html

相关文章

算法复杂度分析

算法复杂度分析

目录 一、计算资源 1、第十三届蓝桥杯 Python 组题目的时空限制汇总 2、Python 与 C/C 、Java 的限制对比 3、时间和空间限制 4、测量代码的运行时间 二、算法定义 1、计算复杂度 2、有哪些复杂度 三、算法评估 1、分类 2、易解问题——难解问题&#xff1a;用多项…
阅读更多...
ArrayList iterator源码分析，为什么迭代器删除元素不会报错

ArrayList iterator源码分析，为什么迭代器删除元素不会报错

写这篇文章的原因要从前不久的一件事说起。 有一天&#xff0c;朋友问我&#xff0c;“ArrayList遍历中删除元素会怎么样”&#xff1f; 我当时脑子里第一想到的就是forEach这种循环方式&#xff0c;没多想就回答他&#xff1a;“当然会报错了。” 朋友再问&#xff1a;“如…
阅读更多...
公司业财一体化详解

公司业财一体化详解

一、传统财务会计如何手工做账1.没有财务系统&#xff08;软件&#xff09;时公司会计用手工记账&#xff0c;流程包括&#xff1a;建立总账&#xff1b;首先建立账簿&#xff0c;登记会计账簿时&#xff0c;应当将会计凭证日期、编号、业务内容摘要、金额和其他有关资料逐项计…
阅读更多...
STM32配置LED模块化

STM32配置LED模块化

文章目录前言一、LED的模块化二、GPIO初始化详细解析三、LED代码封装总结前言 本篇文章将带大家深入了解GPIO的配置&#xff0c;并带大家实现LED模块化编程。 一、LED的模块化 什么叫模块化编程&#xff1f;我的理解就是每一个模块都分别写成对应的.c和.h文件&#xff0c;有…
阅读更多...
【小程序】如何开发属于自己的一款小程序

【小程序】如何开发属于自己的一款小程序

文章目录小程序简介概念小程序与普通网页开发的区别微信开发者工具小程序代码构成项目结构JSON 配置文件WXML 模板WXSS 样式JS 逻辑交互小程序的宿主环境宿主环境简介通信模型运行机制组件常用的视图容器类组件常用的基础内容组件其它常用组件API协同工作小程序成员管理小程序的…
阅读更多...
【计算机模型机设计】8指令多周期（硬布线）MIPS CPU设计报告

【计算机模型机设计】8指令多周期（硬布线）MIPS CPU设计报告

2023年第一篇文章来咯~ 8指令多周期&#xff08;硬布线&#xff09;MIPS CPU设计报告一、设计概述&#xff08;基本类似于上一篇&#xff09;1.1设计目的1.2设计任务1.3设计要求1.4技术指标二、总体方案设计2.1主要功能部件2.2数据通路设计三、详细设计与实现3.1主要功能部件的…
阅读更多...
【Vim】基本操作及命令集详解

【Vim】基本操作及命令集详解

概述 Vim 是从 vi 发展出来的一个文本编辑器。vi 内置在Linux系统中&#xff0c;是vim的简化版编辑器&#xff0c;vim则需要进行安装使用。Vim代码补全、编译及错误跳转等方便编程的功能特别丰富&#xff0c;可以实现高效率移动和高效的输入&#xff0c;在程序员中被广泛使用。…
阅读更多...
用python整个活（5） ——还原方阵游戏

用python整个活（5） ——还原方阵游戏

目录 &#x1f3c6;一、前言 &#x1f3c6;二、游戏规则 &#x1f3c6;三、numpy模块 &#x1f3c6;四、第一步&#xff1a;大循环and获取规格 &#x1f3c6;五、第二步&#xff1a;初始化棋盘 &#x1f3c6;六、第三步&#xff1a;标注矩阵功能&#xff08;难&#xff09; &am…
阅读更多...
最新文章

Copyright @ 2022~2023