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

首先我们要对一组数据进行排序:

在数组中选一个基准数(通常为数组第一个,黄圈圈标记了);

将数组中小于基准数的数据移到基准数左边,大于基准数的移到右边,怎么移动,后面说;

对于基准数左、右两边的数组,不断重复以上两个过程,直到每个子集只有一个元素,即为全部有序。

好了,咱们开始吧!

快速排序需要两个哨兵,i 和 j,分别指向数组的头和尾。接下来就要进行移动。

我们通常选择第一个元素作为基准数,去移动数组元素,使其达到这个基准数的左边都是小于它的,右边都是大于它的。开始移动 i 和 j , i 和 j 是交互移动的,这里我们需要先移动 j,这是为甚呢,原因是先移动 j,等到这一行移动结束,i 的下一个就是 j 的时候,我们先移动 j ,可以避免将数据移动错误,后面会有体会。

当移动 j 时,就开始比较 j 是否比基准数大,如果大于或者等于就 j–,否则再看 i,如果 i 小于等于6,则i++ 再与基准数进行比较,否则 i 就要与 j指向的值互换,我们拿上面那个看

第一步:看j的值比6小,然后看i,i的值是6,所以i++,后面 i继续++,4,3,5都比6小,所以 i 就移动到了7下面。

到这里,j 所指向的值要与 i 所指向的值互换。

互换完成,后面在比较 j 所指向的位置是否比基准数大,如果大就 j–;

这里 7 , 9 ,都比6大,所以j–,进行两次,j 就到达了4的下面。

4比6小,所以要再看 i,i 指向0,所以 i需要 i++,到 1,1也小于6, 所以 i 还需要++,到这里 i 就和 j指向同一个数4,

然后 i = j 了,不能够满足条件,所以就要进行互换,将 i 指向的数,与基准数互换,这一轮比较就结束了,

到这里,基准数6的左边都比6小,右边都比6大。后面还是按照这个来分别再基准数6的左右开始比较。

后面就找这样来,在左右两边再各自将第一个元素作为基准数进行排序。

以此类推,就好了,我把代码贴上。

#include <stdio.h>

#define SIZE 6

//快速排序
void quick_sort(int num[], int low, int high )
{
    int i,j,temp;
    int tmp;

    i = low;
    j = high;
    tmp = num[low];   //任命为中间分界线,左边比他小,右边比他大,通常第一个元素是基准数

    if(i > j)  //如果下标i大于下标j,函数结束运行
    {
        return;
    }

    while(i != j)
    {
        while(num[j] >= tmp && j > i)
        {
            j--;
        }

        while(num[i] <= tmp && j > i)
        {
            i++;
        }

        if(j > i)
        {
            temp = num[j];
            num[j] = num[i];
            num[i] = temp;
        }
    }

    num[low] = num[i];
    num[i] = tmp;

    quick_sort(num,low,i-1);
    quick_sort(num,i+1,high);
}

int main(int argc , char **argv)
{
    //创建一个数组
    int num[SIZE] ={0};
    int i;

    //输入数字
    for(i =0; i < SIZE; i++)
    {
        scanf("%d",&num[i]);
    }

    quick_sort(num, 0, SIZE-1);

    for(i = 0; i < SIZE; i++)
    {
        printf(" %d ", num[i]);
    }

    return 0;
}

总结

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

(0)

相关推荐

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

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

  • C语言中快速排序和插入排序优化的实现

    快速排序 快速排序思想 1962年,由C.A.R.Hoare创造出来.该算法核心思想就一句话:"排序数组时,将数组分成两个小部分,然后对它们递归排序".然而采取什么样的策略将数组分成两个部分是关键,想想看,如果随便将数组A分成A1和A2两个小部分,即便分别将A1和A2排好序,那么A1和A2重新组合成A时仍然是无序的.所以,我们可以在数组中找一个值,称为key值,我们在把数组A分解为A1和A2前先对A做一些处理,让小于key值的元素都移到其左边,所有大于key值的元素都移到其右边.这样递

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

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

  • 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语言快速排序算法示例代码分享

    步骤为:1.从数列中挑出一个元素,称为 "基准"(pivot);2.重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边).在这个分区退出之后,该基准就处于数列的中间位置.这个称为分区(partition)操作.3.递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序.递归的最底部情形,是数列的大小是零或一,也就是永远都已经被排序好了.虽然一直递归下去,但是这个算法总会退出,因为在每次的迭代(iterat

  • C语言的冒泡排序和快速排序算法使用实例

    冒泡排序法 题目描述: 用一维数组存储学号和成绩,然后,按成绩排序输出. 输入: 输入第一行包括一个整数N(1<=N<=100),代表学生的个数.     接下来的N行每行包括两个整数p和q,分别代表每个学生的学号和成绩. 输出: 按照学生的成绩从小到大进行排序,并将排序后的学生信息打印出来.     如果学生的成绩相同,则按照学号的大小进行从小到大排序. 样例输入: 3     1 90     2 87     3 92 样例输出: 2 87     1 90     3 92 代码: #

  • C语言实现快速排序

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

  • 用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;   }  } }}/* * 选择排

  • 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

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

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

随机推荐