C语言简单实现快速排序

2024-11-28 22:23:55

快速排序是一种不稳定排序，它的时间复杂度为O(n·lgn)，最坏情况为O(n2)；空间复杂度为O(n·lgn)。
这种排序方式是对于冒泡排序的一种改进，它采用分治模式，将一趟排序的数据分割成独立的两部分，其中一组数据的每个值都小于另一组。每一趟在进行分类的同时实现排序。

其中每一趟的模式通过设置key当基准元素，key的选择可以是数据的第一个，也可以是数据的最后一个。这里以每次选取数据的第一个为例：

具体代码实现：

#include<stdio.h>
#define N 6
 int fun(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=fun(arr,start,end);
  quick_sort(arr,start,pos-1);
  quick_sort(arr,pos+1,end);
  }
}
int main()
{
  int i;
  int arr[N]={32,12,7,78,23,45};
  for(i=0;i<N;i++)
  {
    printf("%d ",arr[i]);
  }
  printf("\n");
  quick_sort(arr,0,N-1);
  for(i=0;i<N;i++)
  {
    printf("%d ",arr[i]);
  }
  return 0；
 }

由于是第一次撰写博客，许多地方没有一个良好的习惯，还请读者见谅。创建这个博客的目的实际上是为了让自己对于数据结构与算法加深印象，通过博客的形式展现出来一方面方便自己查阅，另一方面以希望能够通过自己的微薄之力帮助到有需要的朋友。

也希望自己能够坚持下去，认真的去做这么一件事。

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。

C语言实现词法分析器

问题描述: 用C或C++语言编写一个简单的词法分析程序,扫描C语言小子集的源程序,根据给定的词法规则,识别单词,填写相应的表.如果产生词法错误,则显示错误信息.位置,并试图从错误中恢复.简单的恢复方法是忽略该字符(或单词)重新开始扫描. 相关词法规则 <标识符>::=<字母> <标识符>::=<标识符><字母> <标识符>::=<标识符><数字> <常量>::＝<无符号整数> <无
C语言实现数独游戏的求解

玩家需要根据9×9盘面上的已知数字,推理出所有剩余空格的数字,并满足每一行.每一列.每一个同色九宫内的数字均含1-9,不重复. 输入包含9x9的已知数字,空位用0补齐,中间用空格隔开.(输入数独题目确保正确) 输出为输入数独题目的解. 样例输入: 8 0 0 0 0 0 0 0 0 0 0 3 6 0 0 0 0 0 0 7 0 0 9 0 2 0 0 0 5 0 0 0 7 0 0 0 0 0 0 0 4 5 7 0 0 0 0 0 1 0 0 0 3 0 0 0 1 0 0 0 0 6 8
如何写出优美的C语言代码

面向对象的语言更接近人的思维方式,而且在很大程度上降低了代码的复杂性,同时提高了代码的可读性和可维护性,传统的 C 代码同样可以设计出比较易读,易维护,复杂度较低的优美代码,本文将通过一个实际的例子来说明这一点. 基础知识结构体除了提供基本数据类型外,C 语言还提供给用户自己定制数据类型的能力,那就是结构体,在 C 语言中,你可以用结构体来表示任何实体.结构体正是面向对象语言中的类的概念的雏形,比如: typedef struct{ float x; float y; }Point; 定义了
C语言数组a和&a的区别讲解

面试经典题目 #include "stdio.h" int main() { int a[5] = { 1,2,3,4,5 }; int *ptr = (int *)(&a + 1); printf("%d,%d", *(a + 1), *(ptr - 1)); /*getchar是用VS编写方便查看输出*/ getchar(); return 0; } 请思考一下上面的输出结果,如果你非常自信了,可以不用往下看题目剖析这个题目主要考察&a 和
使用Python向C语言的链接库传递数组、结构体、指针类型的数据

使用python向C语言的链接库传递数组.结构体.指针类型的数据由于最近的项目频繁使用python调用同事的C语言代码,在调用过程中踩了很多坑,一点一点写出来供大家参考,我们仍然是使用ctypes来调用C语言的代码库. 至于如何调用基础数据类型的数据,请大家参考我的另外一篇文章:Python使用ctypes调用C/C++的方法 1. 使用python给C语言函数传递数组类型的参数想必很多时候,C语言会使用数组作为参数,在之前我们使用过ctypes的一些数据类型作为C语言参数类型,包括byte
C语言程序打豆豆(函数版)

[项目] 设计一个程序,能重复地在显示下面的信息: 1. 吃饭 2. 睡觉 3. 打豆豆 0. 退出请选择(0-3): 根据用户输入的选项,输出一句提示性的话语(将来会对应实现某个功能).输入0,则退出. 要求将各功能定义专门的函数. 参考解答: #include <stdio.h> #define EAT '1' #define SLEEP '2' #define HITDOUDOU '3' #define CRY '4' #define WITHDRAW '0' char getChoi
剑指offer之C语言不修改数组找出重复的数字

1 题目不修改数组找出重复的数字在一个长度为N+1的数组里面的所有数字都在范围1~N范围内,所以数组至少有一个数字是重复的,请找出重复数字,但是不能修改输入的数组. 2 思路思路1: 我们开辟一个新的数组,初始化为0,然后把原始数组每个数据的值作为下标,把新数组通过这个下标数据取出来,如果取出来是1,就说明这个下标数据重复了,如果不是,我们直接放进去,然后进行新数组值进行++操作. 思路2: 比如数据1 2 2 3 4 5 6 7, 我们先找到中间的值(1 + 7) / 2 = 4;然
C语言如何在指针中隐藏数据详解

前言编写 C 语言代码时,指针无处不在.我们可以稍微额外利用指针,在它们内部暗中存储一些额外信息.为实现这一技巧,我们利用了数据在内存中的自然对齐特性. 内存中的数据并非保存在任意地址.处理器通常按照其字大小相同的块读取内存数据:那么考虑到效率因素,编译器会按照块大小的整数倍对内存中的实体进行地址对齐.因此在 32 位的处理器上,一个 4 字节整型数据肯定存放在内存地址能被4整除的地方. 下面,假设系统中整型数据和指针大小均为 4 字节. 现在有一个指向整型的指针.如上所述,整型数据可以存放在
C语言测试n的阶乘和x的n次方

题目描述输入一个正数x和一个正整数n,求下列算式的值.要求定义两个调用函数:fact(n)计算n的阶乘:mypow(x,n)计算x的n次幂(即xn),两个函数的返回值类型是double. ×输出保留4位小数. 输入 x n 输出数列和样例输入 2.0 3 样例输出 1.3333 答案 /************************************************************************* > File Name: 2.c > Author: &
通过GDB学习C语言的讲解

对于那些具有高级编程语言诸如: Ruby.Scheme.Haskell 等背景的人来说,学习 C 语言是具有挑战性的.除了纠结于 C 语言中像手动内存管理和指针等底层特性外,你必须在没有 REPL ( Read-Eval-Print Loop ) 的条件下完成工作.一旦你已经习惯于在 REPL 环境下进行探索性的编程,必须进行"编写-编译-运行"这样循环实在有点令人生厌. 最近我发现其实可以用 GDB 来作为 C 语言的伪 REPL.我一直尝试使用 GDB 作为学习 C 语言的工具,

C语言简单实现快速排序

相关推荐

随机推荐