利用三者取中法改進快速排序，具體內容如下

實現取數組中第一個,中間和最后一個元素的中間元素作為劃分元素(否則將這些元素排除在劃分過程之外).大小為11或更小的數組在劃分過程中被忽略,然后使用插入排序來完成排序.

#include

#include

#include

#include

#include

#include

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;

}

以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持腳本之家。

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的c语言程序设计现代方法快速排序,C语言实现快速排序改进版的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。