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

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

一、快速排序简介

快速排序采用分治的思想,第一趟先将一串数字分为两部分,第一部分的数值都比第二部分要小,然后按照这种方法,依次对两边的数据进行排序。

二、代码实现

#include <stdio.h>

/* 将两个数据交换 */
void swap(int* Ina , int* Inb)
{
  int temp = *Ina;
  *Ina = *Inb;
  *Inb = temp;
}

/* 进行一趟的快速排序,把一个序列分为两个部分 */
int getPartion(int* InArry,int InBegin,int InEnd)
{
  /* 刚开始的分隔线是第一个 */
  int part = InBegin;
  int index = 0;

  if(InEnd >= InBegin)
  {
    part = InBegin;
    for(index = InBegin+1; index <= InEnd; index++)
    {
      if(InArry[InBegin] >= InArry[index])
      {
        /* 交换位置 */
        swap(&InArry[part+1],&InArry[index]);
        part++;
      }
    }

    /* 把第一个数放到part处去 */
    swap(&InArry[InBegin],&InArry[part]);

    return part;
  }

}

/* 快速排序函数
* InArry:输入的数组
* InBegin:数组的开始
*  InEnd:数组的结束
*/
void quickSort(int* InArry,int InBegin,int InEnd)
{
  if(InArry == NULL || InEnd <= InBegin)
  {
    return;
  }

  int part = 0;
  part = getPartion(InArry,InBegin,InEnd);

  /* 递归调用 */
  quickSort(InArry,0,part-1);
  quickSort(InArry,part+1,InEnd);
}

int main()
{
  int a[] = {49,38,65,97,76,13,27};
  int index = 0;

  int len = sizeof(a)/sizeof(int);

  /* 先遍历打印一下数组的元素 */
  for(index = 0; index < len; index++)
  {
    printf("%d ",a[index]);
  }
  printf("\n");

  /* 调用快速排序函数 */
  quickSort(a,0,len-1);

  /* 再遍历打印一下数组的元素 */
  for(index = 0; index < len; index++)
  {
    printf("%d ",a[index]);
  }
  printf("\n");

  return 0;
}

以上就是使用C语言数据结构 快速排序的实例详解,如有疑问请留言或者到本站社区交流讨论,感谢阅读,希望能帮助到大家,谢谢大家对本站 的支持!

(0)

相关推荐

  • C语言数据结构实现链表去重的实例

    C语言数据结构实现链表去重的实例 题目及分析 链表去重 时间限制 300 ms 内存限制 65536 kB 代码长度限制 8000 B 判题程序 Standard 给定一个带整数键值的单链表L,本题要求你编写程序,删除那些键值的绝对值有重复的结点.即对任意键值K,只有键值或其绝对值等于K的第一个结点可以被保留.同时,所有被删除的结点必须被保存在另外一个链表中.例如:另L为21→-15→-15→-7→15,则你必须输出去重后的链表21→-15→-7.以及被删除的链表-15→15. 输入格式: 输入

  • C语言数据结构旋转链表的实现

    C语言数据结构旋转链表的实现 实例: 给出链表1->2->3->4->5->null和k=2 返回4->5->1->2->3->null 分析: 感觉很直观,直接把分割点找出来就行,记得k可能大于len,要取模 代码: /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x

  • C语言数据结构算法之实现快速傅立叶变换

    C语言数据结构算法之实现快速傅立叶变换 本实例将实现二维快速傅立叶变换,同时也将借此实例学习用c语言实现矩阵的基本操作.复数的基本掾作,复习所学过的动态内存分配.文件操作.结构指针的函数调用等内容. 很久以来,傅立叶变换一直是许多领域,如线性系统.光学.概率论.量子物理.天线.数字图像处理和信号分析等的一个基本分析工具,但是即便使用计算速度惊人的计算机计算离散傅立叶变换所花费的时间也常常是难以接受的,因此导致了快速傅立叶变换(FFT)的产生. 本实例将对一个二维数组进行正.反快速傅立叶变换.正傅

  • C语言 数据结构链表的实例(十九种操作)

    C语言 数据结构链表的实例(十九种操作) #include <stdio.h> #include <string.h> #include <stdlib.h> /*************************************************************************************/ /* 第一版博主 原文地址 http://www.cnblogs.com/renyuan/archive/2013/05/21/30915

  • C语言中数据结构之链式基数排序

    C语言中数据结构之链式基数排序 实现效果图: 实例代码: #include<stdio.h> #include<string.h> #include<stdlib.h> #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 typedef int Status; typedef int ElemType; #define MAX_NUM_OF_KEY 8 //关

  • C语言数据结构之栈简单操作

    C语言数据结构之栈简单操作 实验: 编写一个程序实现顺序栈的各种基本运算,并在此基础上设计一个主程序,完成如下功能: (1)初始化顺序栈 (2)插入元素 (3)删除栈顶元素 (4)取栈顶元素 (5)遍历顺序栈 (6)置空顺序栈 分析: 栈的顺序存储结构简称为顺序栈,它是运算受限的顺序表. 对于顺序栈,入栈时,首先判断栈是否为满,栈满的条件为:p->top= =MAXNUM-1,栈满时,不能入栈; 否则出现空间溢出,引起错误,这种现象称为上溢. 出栈和读栈顶元素操作,先判栈是否为空,为空时不能操作

  • C语言数据结构之双向循环链表的实例

    数据结构之双向循环链表 实例代码: #include <stdlib.h> #include <stdio.h> #include <malloc.h> typedef struct Node{ struct Node *pNext; int data; struct Node *prior; } NODE,*PNODE; PNODE CreatList(); void TreNode(PNODE pHead); bool isEmpty(PNODE pHead); i

  • C语言数据结构实现银行模拟

    C语言数据结构实现银行模拟 实现代码: #include <stdio.h> #include <stdlib.h> #include <windows.h> #define MAX_WIN 20 #define MAX_STAY 100 typedef struct customer *link; struct customer { int stay; link next; }; link GUY(int stay, link next) { link c = mal

  • C语言数据结构之循环链表的简单实例

     C语言数据结构之循环链表的简单实例 实例代码: # include <stdio.h> # include <stdlib.h> typedef struct node //定义链表中结点的结构 { int code; struct node *next; }NODE,*LinkList; /*错误信息输出函数*/ void Error(char *message) { fprintf(stderr,"Error:%s/n",message); exit(1)

  • C语言数据结构之中缀树转后缀树的实例

    C语言数据结构之中缀树转后缀树的实例 对于一个中缀表达式 a+b*c*(d-e/f) 转换成后缀是这样的形式 abc*def/-+ 后缀表达式是相当有用处的,转换成后缀表达式后求值会简单很多.那么该如何转换呢? 网上关于这方面的资料一搜一大把,每本数据结构的书中都会提及这个算法,在这个算法中,用到 栈 这个数据结构. 1,关键是比较运算符的优先级,谁的优先级高,谁就出现在前面上面的表达式中,有括号的时候括号优先级最高,*/次之,+-最后. 在上面的表达式中+的优先级不如*的高,因此,在后缀表达式

随机推荐