C语言下快速排序(挖坑法)详解

C语言下快速排序(挖坑法)详解

什么是快速排序

快速排序是将一个待排序的序列分成两部分,其中一部分的所有元素都比另一部分的所有元素小,然后再对这两部分分别进行排序,递归执行该操作直到将整个序列排好为止。快速排序使用了分治思想。由于在每一次的递归过程中,都将待排序的序列分成两部分,因此处理的数据量不断减少,使得算法的效率比较高。

快速排序的实现

挖坑法

挖坑法的基本思想是首先选择一个基准数,用两个标记i和j从序列两端分别向中间扫描,当i遇到了比基准数大的数就停下来,当j遇到了比基准数小的数就停下来,然后交换i和j所指向的元素。直到i和j重合,此时就可以将基准数放在这个位置上,以此将序列分成两个子序列,然后递归地对这两个子序列进行排序。

具体实现的过程如下:

首先选择序列的第一个元素作为基准数pivot,设定i和j的初始值分别为左端点left和右端点right,然后从j开始,向左扫描序列,找出第一个小于基准数的元素,停在j位置上,这时候将pivot的值赋给i,实现了一个“挖坑”操作。接着,从i开始,向右扫描序列,找出第一个大于基准数的元素,停在i位置上,这时候就可以将j位置上的元素填到这个坑中,实现了一个“填坑”操作。随后,i和j再次向中间移动,继续扫描序列,直到i和j重合。最后,将pivot放在i/j重合的位置上,这样就将序列分成了两部分,并以此递归执行。

下面是基于挖坑法的快速排序的代码实现:

void QuickSort(int arr[], int left, int right) {
    if (left >= right) return; // 如果序列只剩下一个元素或者没有元素,则直接返回
    int i = left, j = right, pivot = arr[left]; // 初始化指针i、j,以及基准数pivot
    while (i < j) {
        while (arr[j] >= pivot && i < j) j--;
        if (i < j) arr[i++] = arr[j]; // 挖坑
        while (arr[i] <= pivot && i < j) i++;
        if (i < j) arr[j--] = arr[i]; // 填坑
    }
    arr[i] = pivot; // 将基准数放入最后的空位
    QuickSort(arr, left, i - 1); // 递归排序左边的子序列
    QuickSort(arr, i + 1, right); // 递归排序右边的子序列
}

示例说明

示例一

给定一个数组 arr = {6, 2, 7, 3, 8, 9, 4, 5, 1},使用快速排序对其进行从小到大排序。

首先选定 arr[0],即6作为基准数pivot。然后i和j指向数组的两端 left = 0, right = 8。从j开始,往左寻找第一个小于pivot的数,即找到了 arr[6] = 4,同时将 arr[0] 填上这个坑,得到 arr[0, 2, 7, 3, 8, 9, 4, 5, 4];接着,从i开始,往右寻找第一个大于pivot的数,即找到了 arr[1] = 2,同时将 arr[6] 填上这个坑,得到 arr[2, 2, 7, 3, 8, 9, 6, 5, 4]。i和j在此时重合,将pivot放在这个位置上,得到了 arr[2, 2, 4, 3, 1, 5, 6, 7, 9, 8]。此时将序列分成了两部分,左半部分都小于pivot,右半部分都大于pivot,递归进行排序即可。

经过一次分割后,左半部分为 {2, 2, 4, 3, 1},右半部分为 {5, 6, 7, 9, 8}。以左半部分为例,选择 arr[0] 作为基准数pivot,进行相同的操作,即先从右向左找到一个小于pivot的数 arr[3] = 3,用 arr[0] 填坑,得到 arr[1, 2, 4, 3, 1];接着再从左向右找到第一个大于pivot的数 arr[2] = 4,用 arr[3] 填坑,得到 arr[1, 2, 3, 4, 1]。此时将pivot放在最后的位置上,得到 arr[1, 2, 3, 4, 6]。随后对右半部分进行相似的操作,最终得到完整的排好序的数组 arr[1, 2, 3, 4, 5, 6, 7, 8, 9]

示例二

给定一个数组 arr = {9, 8, 7, 6, 5, 4, 3, 2, 1},使用快速排序对其进行从大到小排序。

首先选定 arr[0],即9作为基准数pivot。然后i和j指向数组的两端 left = 0, right = 8,从j开始寻找小于pivot的数,由于数组本身就是从大到小排列的,因此找不到小于9的数。接着,从i开始寻找大于pivot的数,找到了 arr[1] = 8,用 arr[0] 填坑,得到 arr[9, 9, 7, 6, 5, 4, 3, 2, 1],继续寻找直到i和j重合,最后将pivot放在此位置上,即 arr[8, 9, 7, 6, 5, 4, 3, 2, 1]。此时将序列分成了两部分,左半部分都大于pivot,右半部分都小于pivot,以此递归进行后续排序。

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:C语言下快速排序(挖坑法)详解 - Python技术站

(0)
上一篇 2023年5月19日
下一篇 2023年5月19日

相关文章

  • JS实现的数组全排列输出算法

    JS实现的数组全排列输出算法,一般使用递归实现,具体步骤如下: 步骤一:编写递归函数 首先我们需要定义一个递归函数 permutation,它的输入参数为两个数组: function permutation(arr, result = []) { // … } 其中,arr 是待排列的数组,result 是排列结果。注意,result 是一个可选参数,第…

    算法与数据结构 2023年5月19日
    00
  • 算法之排序算法的算法思想和使用场景总结

    算法之排序算法的算法思想和使用场景总结 一、引言 排序算法是计算机科学基础中的一个重要的部分。随着数据规模的增大,如何高效地对数据进行排序也成为了计算机科学中的重要问题。各种排序算法针对不同的数据结构和数据规模,具有不同的时间和空间复杂度。通过了解不同的排序算法的算法思想和使用场景,可以帮助我们更好地选择合适的排序算法。 二、排序算法的分类 常见的排序算法可…

    算法与数据结构 2023年5月19日
    00
  • STl中的排序算法详细解析

    STl中的排序算法详细解析 概述 在STL中,sort是一种常用的排序算法。sort算法旨在将元素从小到大排序,但也可以使用cmp函数指定排序方式。 算法实现 sort算法基于“快速排序”算法的实现。其基本思想是从待排序列中选取一定的数值作为划分元素(pivot),通过一趟排序将所有比该元素小的数放到它的左边,所有比该元素大的数放到它的右边,然后再对左右两个…

    算法与数据结构 2023年5月19日
    00
  • Java实现快速排序和堆排序的示例代码

    Java实现快速排序和堆排序是经常被面试官提问的面试题目之一。下面是一份攻略,来帮助大家快速掌握这两种排序算法。 快速排序 快速排序(Quick Sort)是一种基于分治思想实现的排序算法,其主要思路是通过分区(Partition)操作将一个数组分成两个子数组,再分别对子数组进行排序,从而达到整个数组有序的目的。 以下是Java实现快速排序的示例代码: pu…

    算法与数据结构 2023年5月19日
    00
  • PHP快速排序quicksort实例详解

    PHP快速排序quicksort实例详解 本文将详细介绍如何使用PHP实现快速排序算法,并提供两个示例进行说明。 基本思路 快速排序是一种比较常见的排序算法,其基本思路是通过递归将待排序数组分割成更小的子数组,并把比基准值小的元素一次放到基准值左边,比基准值大的元素一次放到基准值右边,然后对左右两边分别递归执行上述操作,直到分割成的子数组长度为1,此时由于子…

    算法与数据结构 2023年5月19日
    00
  • go实现冒泡排序算法

    下面是详细讲解Go语言实现冒泡排序算法的完整攻略: 1. 什么是冒泡排序? 冒泡排序是一种基于交换的排序算法,算法通过比较相邻的元素,将比较大的元素交换到后面,从而达到排序的目的。这个过程就像是水中不断上冒的气泡,因此称之为冒泡排序。 冒泡排序是经典的排序算法之一,它虽然时间复杂度高达 O(n^2),但其思想简单,易于理解和实现,并且在某些特殊的情况下,它的…

    算法与数据结构 2023年5月19日
    00
  • JS实现数组随机排序的三种方法详解

    JS实现数组随机排序的三种方法详解 在JavaScript中,实现数组的随机排序是十分常见的需求。本篇文章将讲解三种实现数组随机排序的方法。 方法一:Fisher-Yates算法 Fisher-Yates算法(也被称为 Knuth算法)是实现数组随机排序最常用的算法之一。该算法的思路很简单,即从数组末尾开始,将当前位置的数与它之前的任意一个数交换顺序,直到数…

    算法与数据结构 2023年5月19日
    00
  • JS中的算法与数据结构之列表(List)实例详解

    首先,列表(List)是一种非常常见且重要的数据结构,用于存储一组顺序排列的数据。在JavaScript中,可以通过数组来实现列表。 具体来说,我们可能会涉及到一些常用的列表操作,例如: 在数组尾部添加一个元素 在数组特定位置插入一个元素 从数组中删除指定元素 获取数组中指定位置的元素 下面,我们将结合代码示例,一一介绍这些操作: 在数组尾部添加一个元素 在…

    算法与数据结构 2023年5月19日
    00
合作推广
合作推广
分享本页
返回顶部