C 语言快速排序实例代码

快速排序是对冒泡法排序的一种改进。

快速排序算法 的基本思想是：将所要进行排序的数分为左右两个部分，其中一部分的所有数据都比另外一 部分的数据小，然后将所分得的两部分数据进行同样的划分，重复执行以上的划分操作，直 到所有要进行排序的数据变为有序为止。

可能仅根据基本思想对快速排序的认识并不深，接下来以对n个无序数列A[0], A[1]…, A[n-1]采用快速排序方法进行升序排列为例进行讲解。

(1)定义两个变量low和high，将low、high分别设置为要进行排序的序列的起始元素和最后一个元素的下标。第一次，low和high的取值分别为0和n-1，接下来的每次取值由划分得到的序列起始元素和最后一个元素的下标来决定。

(2)定义一个变量key，接下来以key的取值为基准将数组A划分为左右两个部分，通 常，key值为要进行排序序列的第一个元素值。第一次的取值为A[0]，以后毎次取值由要划 分序列的起始元素决定。

(3)从high所指向的数组元素开始向左扫描，扫描的同时将下标为high的数组元素依次与划分基准值key进行比较操作，直到high不大于low或找到第一个小于基准值key的数组元素，然后将该值赋值给low所指向的数组元素，同时将low右移一个位置。

(4)如果low依然小于high，那么由low所指向的数组元素开始向右扫描，扫描的同时将下标为low的数组元素值依次与划分的基准值key进行比较操作，直到low不小于high或找到第一个大于基准值key的数组元素，然后将该值赋给high所指向的数组元素，同时将high左移一个位置。

(5)重复步骤(3) (4)，直到low的植不小于high为止，这时成功划分后得到的左右两部分分别为A[low……pos-1]和A[pos+1……high]，其中，pos下标所对应的数组元素的值就是进行划分的基准值key，所以在划分结束时还要将下标为pos的数组元素赋值 为 key。

(6)将划分得到的左右两部分A[low……pos-1]和A[pos+1……high]继续采用以上操作步骤进行划分，直到得到有序序列为止。

为了能够加深读者的理解，接下来通过一段代码来了解快速排序的具体实现方法。

#include <stdio.h>
#include <stdlib.h>
#define N 6
int partition(int arr[], int low, int high){
  int key;
  key = arr[low];
  while(low<high){
    while(low <high && arr[high]>= key )
      high--;
    if(low<high)
      arr[low++] = arr[high];
    while( low<high && arr[low]<=key )
      low++;
    if(low<high)
      arr[high--] = arr[low];
  }
  arr[low] = key;
  return low;
}
void quick_sort(int arr[], int start, int end){
  int pos;
  if (start<end){
    pos = partition(arr, start, end);
    quick_sort(arr,start,pos-1);
    quick_sort(arr,pos+1,end);
  }
  return;
}
int main(void){
  int i;
  int arr[N]={32,12,7, 78, 23,45};
  printf("排序前 \n");
  for(i=0;i<N;i++)
    printf("%d\t",arr[i]);
  quick_sort(arr,0,N-1);
  printf("\n 排序后 \n");
  for(i=0; i<N; i++)
    printf("%d\t", arr[i]);
  printf ("\n");
  system("pause");
  return 0;
}

运行结果：

排序前

32    12    7    78    23    45

排序后

7    12    23    32    45    78

在上面的代码中，根据前面介绍的步骤一步步实现了快速排序算法。接下来通过示意图来演示第一次划分操作。

在第一次划分操作中，先进行初始设置，key的值是进行划分的基准，其值为要划分数 组的第一个元素值，在上面的排序序列中为第一个元素值32，同时将low设置为要排序数组中第一个元素的下标，第一次排序操作时其值为0，将high设置为要排序序列最后一个 元素的下标，在上面的排序序列中其第一次取值为5。先将下标为high的数组元素与key进行比较，由于该元素值大于key，因此high向左移动一个位置继续扫描。由于接下来的值为 23，小于key的值，因此将23赋值给下标为low所指向的数组元素。接下来将low右移一 个位置，将low所指向的数组元素的值与key进行比较，由干接下来的12、7都小于key， 因此low继续右移扫描，直至下标low所指向的数组元素的值为78即大于key为止，将78赋值给下标为high所指向的数组元素，同时将high左移一个位置。接下来由于low不再小于high，划分结束。需要注意的是，在进行划分的过程中，都是将扫描的值与key的值进行对比，如果小于key，那么将该值赋值给数组中的另外一个元素，而该元素的值并没有改变。 从图中可以看出这一点，所以需要在划分的最后将作为划分基准的key值赋值给下标为 pos的数组元素，这个元素不再参与接下来的划分操作。

第一次划分操作

第一轮划分结束后，得到了左右两部分序列A[0]、A[1]、A[2]和A[4]、A[5]，继续进 行划分，即对毎轮划分后得到的两部分序列继续划分，直至得到有序序列为止。

以上就是对C语言快速排序的详解,希望能帮助学习 C语言的同学掌握快速排序算法.

赞 (0)

相关推荐

  • C语言实现选择排序、直接插入排序、冒泡排序的示例

    选择排序 选择排序是一种简单直观的排序算法,其核心思想是:遍历数组,从未排序的序列中找到最小元素,将其放到已排序序列的末尾. 时间复杂度:O(n^2) 稳定性 :不稳定 /* * @brief selection sort */ void selection_sort(int a[], int n) { int i, j, min, tmp; for (i = 0; i < n - 1; ++i) { min = i; for (j = i+1; j < n; ++j) { if (a[j]

  • java 合并排序算法、冒泡排序算法、选择排序算法、插入排序算法、快速排序算法的描述

    算法是在有限步骤内求解某一问题所使用的一组定义明确的规则.通俗点说,就是计算机解题的过程.在这个过程中,无论是形成解题思路还是编写程序,都是在实施某种算法.前者是推理实现的算法,后者是操作实现的算法. 一个算法应该具有以下五个重要的特征: 1.有穷性: 一个算法必须保证执行有限步之后结束: 2.确切性: 算法的每一步骤必须有确切的定义: 3.输入:一个算法有0个或多个输入,以刻画运算对象的初始情况: 4.输出:一个算法有一个或多个输出,以反映对输入数据加工后的结果.没有输出的算法是毫无意义的:

  • 简单了解C语言中直接插入排序与直接选择排序实现

    直接插入排序 基本思路: 1. 从a[0]开始,也就是从1个元素开始是有序的,a[1]~a[n-1]是无序的. 2. 从a[1]开始并入前面有序的数组,直到n-1. #include <stdio.h> #define N 5 void insertsort(int a[], int n); void swap(int *x, int *y); void insertsort(int a[], int n){ int i,j; for(i=1; i<n; i++){ for(j=i; j

  • 用c语言实现冒泡排序,选择排序,快速排序

    代码如下所示: 复制代码 代码如下: /* * 冒泡排序 */void BubbleSort(int arr[], int n){ int temp; for (int i = 0; i < n - 1; i++) {  for (int j = i + 1; j < n; j++)  {   if (arr[i] > arr[j])   {    temp = arr[i];    arr[i] = arr[j];    arr[j] = temp;   }  } }}/* * 选择排

  • 深入Java冒泡排序与选择排序的区别详解

    冒泡排序它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来.走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成.代码如下: 复制代码 代码如下: public class nums {     public static void main(String[] args){         int []nums = {5,4,3,2,1};         for(int i = 0; i < nums.length; i++){        

  • C语言实现选择排序、冒泡排序和快速排序的代码示例

    C语言实现选择排序、冒泡排序和快速排序的代码示例

    选择和冒泡 #include<stdio.h> void maopao(int a[],int len){ int i,j,temp; for(i = 0;i < len - 1 ; i ++){//从第一个到倒数第二个 for (j = 0 ; j < len - 1 - i ; j ++)//排在后的是已经排序的 { if (a[j] > a[j + 1])//大的数换到后面去 { temp = a[j]; a[j] = a[j + 1]; a [j + 1] = tem

  • Java中的数组排序方式(快速排序、冒泡排序、选择排序)

    1.使用JavaApi文档中的Arrays类中的sort()进行快速排序 复制代码 代码如下: import java.util.Arrays; public class TestOne{ public static void main(String [] args){ int [] array={2,0,1,4,5,8}; Arrays.sort(array);//调用Arrays的静态方法Sort进行排序,升序排列 for(int show:array){ System.out.printl

  • C 语言快速排序实例代码

    C 语言快速排序实例代码

    快速排序是对冒泡法排序的一种改进. 快速排序算法 的基本思想是:将所要进行排序的数分为左右两个部分,其中一部分的所有数据都比另外一 部分的数据小,然后将所分得的两部分数据进行同样的划分,重复执行以上的划分操作,直 到所有要进行排序的数据变为有序为止. 可能仅根据基本思想对快速排序的认识并不深,接下来以对n个无序数列A[0], A[1]-, A[n-1]采用快速排序方法进行升序排列为例进行讲解. (1)定义两个变量low和high,将low.high分别设置为要进行排序的序列的起始元素和最后一个元

  • Java 冒泡排序、快速排序实例代码

    冒泡排序 冒泡排序是一种简单的排序算法.它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来.走访数列的工作是重复地 进行直到没有再需要交换,也就是说该数列已经排序完成.这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端. 冒泡排序的算法实现如下:[排序后,数组从小到大排列] /** * 冒泡排序 * 比较相邻的元素.如果第一个比第二个大,就交换他们两个. * 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对.在这一点,最后的元素应

  • 比较排序之快速排序(实例代码)

    比较排序之快速排序(实例代码)

    快速排序(简称快排)因为其效率较高(平均O(nlogn))经常在笔试题中对其考查. 对于快排的第一步是选取一个"基数",将会用这个"基数"与其它数进行比较交换.而这个"基数"的选择将影响到快排的效率如何,但如果为了选择基数而选择基数则会本末倒置.例如为了找到最佳基数,则需要在整个待排序列中找到中位数,但查找中位数实际上代价又会很高.基数的选择通常来说就是待排序序列中的第一个对象或者中间的一个对象或者最后一个对象.本文以选取第一个元素为例对快排做一

  • python根据unicode判断语言类型实例代码

    本文实例主要实现的是python根据unicode判断语言类型,具体如下. 实例代码: def is_chinese(uchar): """判断一个unicode是否是汉字""" if uchar >= u'\u4e00' and uchar<=u'\u9fa5': return True else: return False def is_number(uchar): """判断一个unicode是否是

  • SQLite教程（十四）：C语言编程实例代码（2）

    三.高效的批量数据插入: 在给出操作步骤之前先简单说明一下批量插入的概念,以帮助大家阅读其后的示例代码.事实上,批量插入并不是什么新的概念,在其它关系型数据库的C接口API中都提供了一定的支持,只是接口的实现方式不同而已.纵观众多流行的数据库接口,如OCI(Oracle API).MySQL API和PostgreSQL API等,OCI提供的编程接口最为方便,实现方式也最为高效.SQLite作为一种简单灵活的嵌入式数据库也同样提供了该功能,但是实现方式并不像其他数据库那样方便明显,它只是通过一

  • SQLite教程（十三）：C语言编程实例代码（1）

    一.获取表的Schema信息: 1). 动态创建表. 2). 根据sqlite3提供的API,获取表字段的信息,如字段数量以及每个字段的类型. 3). 删除该表. 见以下代码及关键性注释: 复制代码 代码如下: #include <sqlite3.h> #include <string> using namespace std; void doTest() {     sqlite3* conn = NULL;     //1. 打开数据库     int result = sql

  • C语言数据结构 快速排序实例详解

    C语言数据结构 快速排序实例详解 一.快速排序简介 快速排序采用分治的思想,第一趟先将一串数字分为两部分,第一部分的数值都比第二部分要小,然后按照这种方法,依次对两边的数据进行排序. 二.代码实现 #include <stdio.h> /* 将两个数据交换 */ void swap(int* Ina , int* Inb) { int temp = *Ina; *Ina = *Inb; *Inb = temp; } /* 进行一趟的快速排序,把一个序列分为两个部分 */ int getPart

  • c语言5个常用的排序算法实例代码

    1.插入排序 基本思想:插入排序就是每一步都将一个待排数据按其大小插入到已经排序的数据中的适当位置,直到全部插入完毕. void insertSort(vector<int>& nums) { int k = 0; for (int i = 0; i < nums.size(); ++i) { int temp = nums[i]; int j = i; for (; j > 0 && temp < nums[j-1]; --j) nums[j] =

  • C语言中数据结构之链表归并排序实例代码

    C语言中数据结构之链表归并排序实例代码

    C语言中数据结构之链表归并排序实例代码 问题 设有两个无头结点的单链表,头指针分别为ha,hb,链中有数据域data,链域next,两链表的数据都按递增排序存放,现要求将hb表归到ha表中,且归并后ha仍递增序,归并中ha表中已有的数据若hb中也有,则hb中的数据不归并到ha中,hb的链表在算法中不允许破坏. 源程序 #include <stdio.h> #include<stdlib.h> #define N1 6 /*链表La的长度*/ #define N2 6 /*链表Lb的

  • C++语言数据结构 串的基本操作实例代码

    C++语言数据结构 串的基本操作实例代码

    C语言数据结构 串的基本操作实例代码 输出结果: 实现代码: #include<iostream> using namespace std; typedef int Status; #define Max 20 #define OK 1 #define ERROR 0 #define OVERLOE -2 typedef struct//堆分配表示串 { char *ch; int length; }HString; //====================================

随机推荐