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)
 {
  while(i < j)
  {
   while((a[j] >= temp) && (i < j))
   {
    j--;
   }
   a[i] = a[j];
   while((a[i] <= temp) && (i < j))
   {
    i++;
   }
   a[j]= a[i];
  }
  a[i] = temp;
  quiksort(a,low,i-1);
  quiksort(a,j+1,high);
 }
 else
 {
  return;
 }
}
int search(int x, int v[], int n){
 int low, high, mid;
 low = 0;
 high = n - 1;
 while ( low <= high ) {
  mid = (low + high) / 2;
  if(x < v[mid]){
   high = mid - 1;
  }
  else if(x > v[mid]){
   low = mid + 1;
  }
  else{
   return mid;
  }
 }
 return -1;
}
int main(){
 int arry[100] ;
 int i,j;
 srand((unsigned)time(NULL)); //产生不同的随机数
 for(i=0;i<100;i++)
 {
  j = rand()%100;
  //if(i%2==0) //产生负数
  //j =-j;
  arry[i]=j;
 }
 int location;
 int number ;
 quiksort(arry,0,99);//随机数先进行排序
 for(i=0;i<100;i++)
 {
  printf("%d ",arry[i]);
 }
 printf("\n");
 printf("请输入你要查找的数字");
 scanf("%d",&number);
 location = search(number, arry, 100);
 printf("%d\n", location);
 return 0;
}

心得与体会:

二分查找比较容易理解,就是折半查找法,所以要求数据必须是有序数列。不断比较中间值。

快速排序是应用了递归,首先确定一个关键数据,再把比他大的放到后面,比他小的放到前面,再分别对这两部分进行同样的操作。

希望本文所述对大家C语言程序设计有所帮助。

(0)

相关推荐

  • 用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语言中快速排序和插入排序优化的实现

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

  • C语言中使用快速排序算法对元素排序的实例详解

    调用C语言的快速排序算法qsort(); #include<stdio.h> #include<stdlib.h> #include<string.h> #define SIZE 100 //从小到大排序 int comp1(const void *x,const void *y) { return *(int *)x - *(int *)y; } //从大到小排序 int comp2(const void *x,const void *y) { return *(in

  • c语言快速排序算法示例代码分享

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

  • 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语言使用stdlib.h库函数的二分查找和快速排序的实现代码

    快速排序: 复制代码 代码如下: #include <stdlib.h>#include <stdio.h>#include <string.h> #define LENGTH(x) sizeof(x)/sizeof(x[0]) /**输出数组元素*\param arr:指向数组的指针*\param len:数组元素的个数*/void print(char (*arr)[10],int len){    int i;    for (i=0;i<len;i++) 

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

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

  • 纯C语言:分治快速排序源码分享

    复制代码 代码如下: #include<stdio.h>void fun(int array[],int low,int high){    int i = low;    int j = high;      int temp = array[i];              while(i < j)     {  while((array[j] >= temp) && (i < j))  {    j--;    array[i] = array[j]; 

  • 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语言的冒泡排序和快速排序算法使用实例

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

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

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

随机推荐