C语言实现快速排序算法

一、快速排序算法（Quicksort）

1. 定义

快速排序由C. A. R. Hoare在1962年提出。快速排序是对冒泡排序的一种改进，采用了一种分治的策略。

2. 基本思想

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

3. 步骤

a. 先从数列中取出一个数作为基准数。

b. 分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。

c. 再对左右区间重复第二步，直到各区间只有一个数。

二、C语言实现代码（仅供参考）

 
#include 
#include 
 
#define BUF_SIZE 10
 

void display(int array[], int maxlen)
{
  int i;
 
  for(i = 0; i < maxlen; i++)
  {
    printf("%-3d", array[i]);
  }
  printf("n");
 
  return ;
}
 

void swap(int *a, int *b) 
{
  int temp;
 
  temp = *a;
  *a = *b;
  *b = temp;
 
  return ;
}
 

void quicksort(int array[], int maxlen, int begin, int end)
{
  int i, j;
 
  if(begin < end)
  {
    i = begin + 1; // 将array[begin]作为基准数，因此从array[begin+1]开始与基准数比较！
    j = end;    // array[end]是数组的最后一位
     
    while(i < j)
    {
      if(array[i] > array[begin]) // 如果比较的数组元素大于基准数，则交换位置。
      {
 swap(&array[i], &array[j]); // 交换两个数
 j--;
      }
      else
      {
 i++; // 将数组向后移一位，继续与基准数比较。
      }
    }
 
    
 
    if(array[i] >= array[begin]) // 这里必须要取等“>=”，否则数组元素由相同的值时，会出现错误！
    {
      i--;
    }
 
    swap(&array[begin], &array[i]); // 交换array[i]与array[begin]
    
    quicksort(array, maxlen, begin, i);
    quicksort(array, maxlen, j, end);
  }
}
 
// 主函数
int main()
{
  int n;
  int array[BUF_SIZE] = {12,85,25,16,34,23,49,95,17,61};
  int maxlen = BUF_SIZE;
  
  printf("排序前的数组n");
  display(array, maxlen);
  
  quicksort(array, maxlen, 0, maxlen-1); // 快速排序
  
  printf("排序后的数组n");
  display(array, maxlen);
  
  return 0;
}

执行程序后的结果如下所示：

上诉代码结合了我自己对快速排序的看法和理解，仅供参考。

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