C语言实现快速排序改进版

利用三者取中法改进快速排序,具体内容如下

实现取数组中第一个,中间和最后一个元素的中间元素作为划分元素(否则将这些元素排除在划分过程之外).大小为11或更小的数组在划分过程中被忽略,然后使用插入排序来完成排序.

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <queue>
#include <malloc.h>
using namespace std;
#define OK 1
#define ERROR -1
#define TRUE 1
#define FALSE 0
typedef int Status;
//输出函数
void Print(int a[], int l, int r)
{
 int i;
 for(i = l; i <= r; i++)
 {
  printf("%d ", a[i]);
 }
 printf("\n");
}
//插入排序的改进
void Insertion(int a[], int l, int r)
{
 int i, j;
 //循环找到数组中的最小值
 for(i = r; i > l; i--)
 {
  if(a[i-1] > a[i])
  {
   swap(a[i-1], a[i]);
  }
 }
 //由于上面的循环,a[0]a[1]已经有序
 for(i = l+2; i <= r; i++)
 {
  int temp = a[i];
  j = i;
  //此时a[j]的位置已被记录
  //while循环比较进行移位操作
  while(temp < a[j-1])
  {
   a[j] = a[j-1];
   j--;
  }
  //将记录下的值放到应当的位置
  a[j] = temp;
 }
}
//划分函数
int partion(int a[], int left, int right)
{
 //取最右边的元素作划分元素
 int temp = a[right];
 //记录 i = left, j = right
 int i = left, j = right-1;
 //循环直到左右指针相遇
 while(true)
 {
  //从左边开始扫描,当出现比划分元素大的元素,扫描停止
  while(temp > a[i])
  {
   i++;
  }
  //从右边进行扫描,当出现比划分元素小的元素,扫描停止
  while(temp < a[j] && j >= left)
  {
   j--;
  }
  //如果 i >= j, 循环截止,下面的交换不执行
  if(i >= j) break;
  //交换停止时的元素
  swap(a[i], a[j]);
 }
 //交换该元素与划分元素
 swap(a[i], a[right]);
 //printf("i = %d\n", i);
 //Print(a, 0, 6);
 //划分过程结束
 return i;
}

void qsort(int a[], int left, int right)
{
 int i;
 if(right-left <= 10)
  return;
 swap(a[(left+right)/2], a[right-1]);
 if(a[left] > a[right-1])
  swap(a[left], a[right-1]);
 if(a[left] > a[right])
  swap(a[left], a[right]);
 if(a[right] > a[right-1])
  swap(a[right-1], a[right]);
 i = partion(a, left+1, right-1);
 qsort(a, left, i-1);
 qsort(a, i+1, right);
}
void Sort(int a[], int left, int right)
{
 qsort(a, left, right);
 Insertion(a, left, right);
}

int main()
{
 int a[12] = {2, 5, 3, 7, 6, 1, 4, 11, 8, 10, 9, 12};
 //快速排序改进
 printf("对0~11排序\n");
 Sort(a, 0, 11);
 Print(a, 0, 11);
 return 0;
}

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

(0)

相关推荐

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

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

  • C语言实现快速排序

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

  • C语言对堆排序一个算法思路和实现代码

    算法思想简单描述: 堆排序是一种树形选择排序,是对直接选择排序的有效改进. 堆的定义如下:具有n个元素的序列(h1,h2,...,hn),当且仅当满足(hi>=h2i,hi>=2i+1)或(hi<=h2i,hi<=2i+1)(i=1,2,...,n/2)时称之为堆.在这里只讨论满足前者条件的堆. 由堆的定义可以看出,堆顶元素(即第一个元素)必为最大项.完全二叉树可以很直观地表示堆的结构.堆顶为根,其它为左子树.右子树. 初始时把要排序的数的序列看作是一棵顺序存储的二叉树,调整它们的

  • c语言实现冒泡排序、希尔排序等多种算法示例

    实现以下排序 插入排序O(n^2) 冒泡排序 O(n^2) 选择排序 O(n^2) 快速排序 O(n log n) 堆排序 O(n log n) 归并排序 O(n log n) 希尔排序 O(n^1.25) 1.插入排序 O(n^2) 一般来说,插入排序都采用in-place在数组上实现.具体算法描述如下:⒈ 从第一个元素开始,该元素可以认为已经被排序⒉ 取出下一个元素,在已经排序的元素序列中从后向前扫描⒊ 如果该元素(已排序)大于新元素,将该元素移到下一位置⒋ 重复步骤3,直到找到已排序的元素

  • c语言冒泡排序法代码

    总在写 总在错, 面试也还忘记 学习就是这么个过程, 温故才知新, 望自己谨记 忘记不要紧 复习就好 //排序是有很多种方法的 ,完成从小到大的排列 复制代码 代码如下: #include <stdio.h>void sort(int *a,int len){int i=0; int j; int t;    for(i=0;i<len;i++)    {        for(j=0;j<len-i-1;j++)        {            if(a[j]>a[

  • C语言实现排序算法之归并排序详解

    排序算法中的归并排序(Merge Sort)是利用"归并"技术来进行排序.归并是指将若干个已排序的子文件合并成一个有序的文件. 一.实现原理: 1.算法基本思路 设两个有序的子文件(相当于输入堆)放在同一向量中相邻的位置上:R[low..m],R[m+1..high],先将它们合并到一个局部的暂存向量R1(相当于输出堆)中,待合并完成后将R1复制回R[low..high]中. (1)合并过程 合并过程中,设置i,j和p三个指针,其初值分别指向这三个记录区的起始位置.合并时依次比较R[i

  • 用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语言合并两个已排序数组的示例(c语言数组排序)

    问题:将两个已排序数组合并成一个排序数组 这里先不考虑大数据量的情况(在数据量很大时不知大家有什么好的思路或方法?),只做简单数组的处理. 简单代码如下: 说明:之所以把merge函数定义成返回数组长度,是因为后续会有重复数据合并功能的merge版本,考虑到接口一致性. 复制代码 代码如下: #include <stdio.h>#include <stdlib.h>#include <string.h> int merge(int* ar1, int len1, int

  • 合并排序(C语言实现)

    其基本模式如下: 分解:把一个问题分解成与原问题相似的子问题 解决:递归的解各个子问题 合并:合并子问题的结果得到了原问题的解. 现在就用递归算法,采用上面的分治思想来解合并排序. 合并排序(非降序) 分解:把合并排序分解成与两个子问题 伪代码: 复制代码 代码如下: MERGE_SORT(A, begin, end) if begin < end then mid<- int((begin + end)/2) MERGE_SORT(A, begin, mid) MERGE_SORT(A, m

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

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

随机推荐