数据结构中快速排序的程序和算法，望大神帮我改改。。。。

为什么没有变化呢？

是因为你的数组信息存储到了Laelem,但是快排却是对Lar进行排序，然后遍历又是对Laelem遍历输出，所以一直没有改变！

另外，快排写的也有问题，存储的时候是Laelem[0]~Laelem[length-1]，排序的时候却对1~LaLength进行排序，附上修改后的程序，希望能有帮助。

//前半部自定义paixuh文件

#include<iostream>

using namespace std;

const int Maxsize=5;

typedef int InfoType;

typedef int KeyType;

typedef int ElemType;

const int LIST_INIT_SIZE = 100;

const int LISTINCREMENT = 10;

typedef struct{

KeyType key;

//InfoType otherinfo;

}Rcdtype;

typedef struct{

Rcdtype r[Maxsize+1];

int length;

ElemType elem;

int listsize;

int incrementsize;

}SqList;

//初始化

void InitList(SqList &L, int maxsize = LIST_INIT_SIZE, int incresize = LISTINCREMENT)

{

Lelem = new ElemType[maxsize];

Llength = 0;

Llistsize = maxsize;

Lincrementsize = incresize;

}

//定义度函数length

int Listlength(SqList L)

{

return(Llength);

}

//插入

void ListInsert(SqList &L, int i, ElemType e)

{   Rcdtype q;

Rcdtype p;

if(i<1 || i>Llength + 1)  ;

//if(Llength >= Llistsize) increment(L);

q = &(Lr[i-1]);

for(p = &(Lr[Llength - 1]);p >= q; --p) (p+1) = p;

(q)key = e;

++Llength;

}

// 输

void ListTraverse(SqList L)

{   for(int i=0; i<Llength; i++)

{

cout<<Lr[i]key<<" ";

}

cout<<endl;

}

//面始主程序cpp希望神帮我改改（注 vc++运行）

int Partition(Rcdtype R,int low ,int high)

{   int pivotkey;

Rcdtype t=R[low];

pivotkey=R[low]key;

while(low<high)

{

while(low<high && R[high]key>=pivotkey) --high;

R[low]=R[high];

while(low<high && R[low]key<=pivotkey) ++low;

R[high]=R[low];

}//while

R[low]=t;

return low;

}//Partition

void Qsort(Rcdtype R,int s,int t)

{   int pivotloc;

if(s<t)

{pivotloc=Partition(R,s,t);

Qsort(R,s,pivotloc-1);

Qsort(R,pivotloc+1,t);

}

}//Qsort

void Quicksort(SqList &L)

{

Qsort(Lr,0,Llength-1);

}//Quicksort

int  main()

{

SqList La;

int m;

InitList(La);

ListInsert(La,1,1);

ListInsert(La,2,2);

ListInsert(La,1,3);

ListInsert(La,3,4);//输3 1 4 2

//ListInsert(La,1,5);

cout<<"排序前La"<<endl;

ListTraverse(La);

cout<<"\n排序La"<<endl;

Quicksort(La);

ListTraverse(La);

}

首先要写正确。通常使用递归实现。其递归相当于二叉树展开，因此如果要用迭代实现的话需要使用一个队列来保存后续遍历信息。

快速排序需要找到一个pivot值，如果顺序选择pivot则易造成N^2的复杂度，如果使用随机数则效果最好，但开销又太大，采取三数中值法比较合适。三数中值法指的是选取第一个值，最后一个值，数组中间的值的中值。有文献表明可以提升5%的运行时间。

当数组长度较小时，如10个元素以下，最好使用插入排序或者选择排序完成，以防止复杂度常数因子过大或多次函数调用带来的开销。而递归到底层数组长度总是会变小的，因此这么做非常有必要。

在合并前后两部分数组时，采用两边夹方法，在前后两部分各找到一个大于和小于的值再交换。相比通常情况下找到比pivot小的值就进行交换，能提高运行效率。

第一遍 12 31 54 65 32 34 45 68 75 85 43 77 98第二遍 12 31 54 65 32 34 45 68 75 85 43 77 98第三遍 12 31 32 34 45 43 54 98 77 85 75 68 65第四遍 12 31 32 34 45 43 54 98 77 85 75 68 65第五遍 12 31 32 34 45 43 54 98 77 85 75 68 65第六遍 12 31 32 34 43 45 54 98 77 85 75 68 65第七遍 12 31 32 34 43 45 54 98 77 85 75 68 65 （左边区间所有递归完成，开始右边区间逐一递归）第八遍 12 31 32 34 43 45 54 65 68 75 85 77 98 第九遍 12 31 32 34 43 45 54 65 68 75 85 77 98第十遍 12 31 32 34 43 45 54 65 68 75 85 77 98第十一遍 12 31 32 34 43 45 54 65 68 75 85 77 98第十二遍 12 31 32 34 43 45 54 65 68 75 77 85 98第十三遍12 31 32 34 43 45 54 65 68 75 77 85 98 快速算法每次取当前无序区的第一个记录为基准，首先取12作为tep量，起始位置i=0，终止位置j=12最外层循环，只要i 不等于 j 就扫描，内层循环，首先从右向左扫描，找到第一个小于tep的值，再交换这个值和tep，这样tep的左边都是比他小的数，再从左向右扫描，找到第1个大于tep的值，与tep交换，这样右边都是比tep大的数。接下来，递归此程序，用同样方法快速排序那个tep值的左区间和右区间。可以看做是，先得出无序区第一个在此序列里应有的位置，再依此位置为轴，排序左右区间，又分别得出左右无序区间的第一个值在序列里的应有位置。

void quicksort(int p,int m,int n)

{

if (m==n||m==n-1) return;

int i=partition(p,m,n);

quicksort(p,i+1,n);

quicksort(p,m,i);

} partition函数这里写不下，你自己想想吧

快速排序（Quicksort）是对冒泡排序的一种改进。[1]

快速排序由C A R Hoare在1960年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。[1]

中文名

快速排序算法

外文名

quick sort

别名

快速排序

提出者

C A R Hoare

提出时间

1960年

快速

导航

排序步骤

程序调用举例

示例代码

性能分析

排序流程

快速排序算法通过多次比较和交换来实现排序，其排序流程如下：[2]

(1)首先设定一个分界值，通过该分界值将数组分成左右两部分。[2]

(2)将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。[2]

(3)然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。[2]

(4)重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。[2]

排序步骤

原理

设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据（通常选

快排图

用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它左边，所有比它大的数都放到它右边，这个过程称为一趟快速排序。值得注意的是，快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。[1]

一趟快速排序的算法是：[1]

1）设置两个变量i、j，排序开始的时候：i=0，j=N-1；[1]

2）以第一个数组元素作为关键数据，赋值给key，即key=A[0]；[1]

3）从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于key的值A[j]，将A[j]和A[i]的值交换；[1]

4）从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]和A[j]的值交换；[1]

5）重复第3、4步，直到i==j； (3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。[1]

排序演示

假设一开始序列{xi}是：5，3，7，6，4，1，0，2，9，10，8。

此时，ref=5，i=1，j=11，从后往前找，第一个比5小的数是x8=2，因此序列为：2，3，7，6，4，1，0，5，9，10，8。

此时i=1，j=8，从前往后找，第一个比5大的数是x3=7，因此序列为：2，3，5，6，4，1，0，7，9，10，8。

此时，i=3，j=8，从第8位往前找，第一个比5小的数是x7=0，因此：2，3，0，6，4，1，5，7，9，10，8。

以上就是关于数据结构中快速排序的程序和算法，望大神帮我改改。。。。全部的内容，包括:数据结构中快速排序的程序和算法，望大神帮我改改。。。。、如何写出一个较好的快速排序程序、快速排序法如何排序等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！