C语言之快速排序案例详解

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

它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

例如有一个数字序列： 5 0 1 6 8 2 3 4 9 7
对其进行快速排序变为：0 1 2 3 4 5 6 7 8 9

思路如下：首先将要排序的序列的首个数字5定位比较数，这是一个参考对象！

然后的方法很简单：分别从序列的两端进行比较。先从右边往左边找比5小的数，再从左边往右边找大于5的数。当他们找到以后就需要停下来，然后交换它们。
在这里我们为了方便，将i定为左边，j为右边。

接下来继续前进，还是先从右边。
接下来得到的序列如下：
5 0 1 4 3 2 8 6 9 7

当它继续下去的时候我们可以知道这时,i,j相遇了。

这个时候，直接将比较数与相遇的数进行交换

得到如下序列：2 0 1 4 3 5 8 6 9 7

可以看出，在右边的数都比比较数5大，左边的数都比比较数5小。

这个时候其实就是第一轮排序结束了。

下面的排序就是将左边与右边分别看成两个序列，然后与上面的一样进行排序。这里其实就是应用到了递归！

完整代码如下：

#include<stdio.h>
int a[100];//这里将数组a定义为全局变量，方便后面使用
void kspx(int left,int right)
{
    int i,j;
    int t,bjs;//bjs就是指开头的比较数
    if(left>right)
        return;
    bjs=a[left];
    i=left;
    j=right;
    while(i!=j)
    {
        while (a[j]>=bjs&&i<j)//这里是从右往左走
            j--;
        while(a[i]<=bjs&&i<j)//这里是从左往右走
            i++;
        if(i<j)//当i,j还没有相遇的时候
        {
            t=a[i];
            a[i]=a[j];
            a[j]=t;
        }
    }
    a[left]=a[i];//将比较数换到i,j相遇的位置
    a[i]=bjs;
    kspx(left,i-1);//下面使用递归进行下面的排序
    kspx(i+1,right);//使其排好
}
int main()
{
    int i,j;
    int n;
    scanf("%d",&n);//首序列长度
    for(i=1;i<=n;i++)
    scanf("%d",&a[i]);
    kspx(1,n);//快速排序函数
    for(i=1;i<=n;i++)//验证结果
        printf("%d ",a[i]);
    return 0;
}

结果如下：

总结：快速排序的优点是速度快，缺点是不稳定。

到此这篇关于C语言之快速排序案例详解的文章就介绍到这了,更多相关C语言之快速排序内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C语言实现快速排序算法

    C语言实现快速排序算法

    一.快速排序算法(Quicksort) 1. 定义 快速排序由C. A. R. Hoare在1962年提出.快速排序是对冒泡排序的一种改进,采用了一种分治的策略. 2. 基本思想 通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列. 3. 步骤 a. 先从数列中取出一个数作为基准数. b. 分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全

  • C语言简单实现快速排序

    快速排序是一种不稳定排序,它的时间复杂度为O(n·lgn),最坏情况为O(n2):空间复杂度为O(n·lgn). 这种排序方式是对于冒泡排序的一种改进,它采用分治模式,将一趟排序的数据分割成独立的两部分,其中一组数据的每个值都小于另一组.每一趟在进行分类的同时实现排序. 其中每一趟的模式通过设置key当基准元素,key的选择可以是数据的第一个,也可以是数据的最后一个.这里以每次选取数据的第一个为例: 具体代码实现: #include<stdio.h> #define N 6 int fun(i

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

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

  • C语言对磁盘文件进行快速排序简单实例

    C语言对磁盘文件进行快速排序简单实例 快速排序(quick sort)是由C.A.R.Hoare发明并命名的,这种排序被认为是目前最好的一种排序算法.快速排序基于交换排序,与同样的基于交换排序的冒泡排序法相比,其效果非常明显. 它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列. 本例中快速排序是通过函数quick_disk(FILE

  • C语言实现快速排序改进版

    利用三者取中法改进快速排序,具体内容如下 实现取数组中第一个,中间和最后一个元素的中间元素作为划分元素(否则将这些元素排除在划分过程之外).大小为11或更小的数组在划分过程中被忽略,然后使用插入排序来完成排序. #include <cstdio> #include <cstdlib> #include <algorithm> #include <stack> #include <queue> #include <malloc.h> u

  • C语言快速排序函数用法（qsort）

    本文实例为大家分享了C语言快排函数用法,供大家参考,具体内容如下 #include <stdio.h> #include <stdlib.h> #include <string.h> struct student { int id; char name[12]; char sex; }; int compare(const void* a,const void* b)//基本数据类型排序 { return *(char*)a-*(char*)b;//从小到大 //取值/

  • C语言快速排序与二分查找算法示例

    本文实例讲述了C语言二分排序与查找算法.分享给大家供大家参考,具体如下: 题目:首先产生随机数,再进行快速排序,再进行二分查找. 实现代码: #include <stdio.h> #include <stdlib.h> #include <time.h> void quiksort(int a[],int low,int high) { int i = low; int j = high; int temp = a[i]; if( low < high) { wh

  • C语言实现快速排序

    快速排序算法是一种分治排序算法.它将数组划分为两个部分,然后分别对两个部分进行排序.我们将看到,划分的准确位置取决于输入数组中元素的初始位置.关键在于划分过程,它重排数组,使得以下三个条件成立:(i)对于某个i,a[i]在最终位置上 (ii)a[left],...,a[i-1]中的元素都比a[i]小 (iii)a[i+1],...a[right]中的元素都比a[i]大.我们通过划分来完成排序,然后递归地应用该方法处理子数组. 我们使用一般策略来实现划分.首先,我们任选一个a[right]作为划分

  • C语言之快速排序案例详解

    C语言之快速排序案例详解

    快速排序:是对冒泡排序算法的一种改进. 它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列. 例如有一个数字序列: 5 0 1 6 8 2 3 4 9 7 对其进行快速排序变为:0 1 2 3 4 5 6 7 8 9 思路如下:首先将要排序的序列的首个数字5定位比较数,这是一个参考对象! 然后的方法很简单:分别从序列的两端进行比较.先

  • C语言指针数组案例详解

    指针与数组是 C 语言中很重要的两个概念,它们之间有着密切的关系,利用这种 关系,可以增强处理数组的灵活性,加快运行速度,本文着重讨论指针与数组之 间的联系及在编程中的应用. 1．指针与数组的关系 当一个指针变量被初始化成数组名时,就说该指针变量指向了数组.如: char str[20], *ptr; ptr=str; ptr 被置为数组 str 的第一个元素的地址,因为数组名就是该数组的首地址, 也是数组第一个元素的地址.此时可以认为指针 ptr 就是数组 str(反之不成立), 这样原来对数

  • C语言strtod()函数案例详解

    C语言strtod()函数案例详解

    前言 网上有很多关于strtod()函数的文章,不过大部分都是用strtod()函数转换一个字符 char *str = "111.11"; char *target; double ret; ret = strtod(str, &target); 很少有转换字符串的这样的用法 char *p = "111.11 -2.22 Nan nan(2) inF 0X1.BC70A3D70A3D7P+6 1.18973e+4932zzz"; 本文主要参考strtod

  • C语言求逆矩阵案例详解

    一般求逆矩阵的方法有两种,伴随阵法和初等变换法.但是这两种方法都不太适合编程.伴随阵法的计算量大,初等变换法又难以编程实现. 适合编程的求逆矩阵的方法如下: 对可逆矩阵A进行QR分解:A=QR 求上三角矩阵R的逆矩阵 求出A的逆矩阵:A^(-1)=R^(-1)Q^(H) 以上三步都有具体的公式与之对应,适合编程实现. C语言实现代码: #include <stdio.h> #include <math.h> #define SIZE 8 double b[SIZE][SIZE]={

  • C语言实现矩阵运算案例详解

    C语言实现矩阵运算案例详解

    C语言实现矩阵运算 给定一个n×n的方阵,本题要求计算该矩阵除副对角线.最后一列和最后一行以外的所有元素之和.副对角线为从矩阵的右上角至左下角的连线. 输入格式: 输入第一行给出正整数n(1<n≤10):随后n行,每行给出n个整数,其间以空格分隔. 输出格式: 在一行中给出该矩阵除副对角线.最后一列和最后一行以外的所有元素之和. 输入样例: 4 2 3 4 1 5 6 1 1 7 1 8 1 1 1 1 1 输出样例: 35 #include <stdio.h> #include <

  • C语言 TerminateProcess函数案例详解

    TerminateProcess 顾名思义,就是终止进程的意思. 是WindowsAPI的函数, 示例代码如下: // Demo.cpp : 定义控制台应用程序的入口点. //终止进程Demo #include "stdafx.h" using namespace std; //@param:dwpid:指定需要关闭的进程pid int CloseProcess(DWORD dwpid) { HANDLE hProcess = OpenProcess(PROCESS_TERMINATE

  • C语言 bind()函数案例详解

    bind()函数介绍        在建立套接字文件描述符成功后,需要对套接字进行地址和端口的绑定,才能进行数据的接收和发送操作. 函数原型        bind()函数将长度为addlen的struct sockadd类型的参数my_addr与sockfd绑定在一起,将sockfd绑定到某个端口上,如果使用connect()函数则没有绑定的必要.绑定的函数原型如下: #include<sys/types.h> #include<sys/socket.h> int bind(in

  • C语言 动态分配数组案例详解

    C语言 动态分配数组案例详解

    目录 一维动态数组的创建: 二维数组的创建: 很多人在编写C语言代码的时候很少使用动态数组,不管什么情况下通通使用静态数组的方法来解决,在当初学习C语言的时候我就是一个典型的例子,但是现在发现这是一个相当不好的习惯,甚至可能导致编写的程序出现一些致命的错误.尤其对于搞嵌入式的人来所,嵌入式系统的内存是宝贵的,内存是否高效率的使用往往意味着嵌入式设备是否高质量和高性能,所以高效的使用内存对我们来说是很重要的.那么我们在自己编写C语言代码的时候就应该学会使用动态数组,这也就是我这篇博客要给大家讲的,

  • C语言 CRITICAL_SECTION用法案例详解

          很多人对CRITICAL_SECTION的理解是错误的,认为CRITICAL_SECTION是锁定了资源,其实,CRITICAL_SECTION是不能够"锁定"资源的,它能够完成的功能,是同步不同线程的代码段.简单说,当一个线程执行了EnterCritialSection之后,cs里面的信息便被修改,以指明哪一个线程占用了它.而此时,并没有任何资源被"锁定".不管什么资源,其它线程都还是可以访问的(当然,执行的结果可能是错误的).只不过,在这个线程尚未执

随机推荐