c++ 链表快速排序 C++ 快排
采用数组排序，使用快速排序，例如说采用a 关键字排序的话:
void Swap(Type &NodeA,Type &NodeB)
{
Type Temp=NodeA;
NodeA=NodeB;
NodeB=Temp;
}
void Qsort(int LeftRange,int RightRange,Type Array[])
{
int LPoint,RPoint;
unsigned int Mid;
if (LeftRange==RightRange) return ;
Mid=Array[(LeftRange+RightRange)/2].a;
LPoint=LeftRange;RPoint=RightRange;
do
{
LPoint++;RPoint--;
while (Array[LPoint].a<Mid) LPoint++;
while (Array[RPoint].a>Mid) RPoint--;
if (LPoint<RPoint)
{
Swap(Array[LPoint],Array[RPoint]);
}
}while (LPoint<RPoint);
Qsort(LeftRange,RPoint);
Qsort(RPoint+1,RightRange);
}
从大到小排序：
采用数组排序，使用快速排序，例如说采用a 关键字排序的话:
void Swap(Type &NodeA,Type &NodeB)
{
Type Temp=NodeA;
NodeA=NodeB;
NodeB=Temp;
}
void Qsort(int LeftRange,int RightRange,Type Array[])
{
int LPoint,RPoint;
unsigned int Mid;
if (LeftRange==RightRange) return ;
Mid=Array[(LeftRange+RightRange)/2].a;
LPoint=LeftRange;RPoint=RightRange;
do
{
LPoint++;RPoint--;
while (Array[LPoint].a>Mid) LPoint++;
while (Array[RPoint].a<Mid) RPoint--;
if (LPoint<RPoint)
{
Swap(Array[LPoint],Array[RPoint]);
}
}while (LPoint<RPoint);
Qsort(LeftRange,RPoint);
Qsort(RPoint+1,RightRange);
}
插入排序的时间复杂度是O(N^2)的时间复杂度，而快速排序的平均复杂度为O(N*Log(N))，且快速排序的时间常数小，虽然其最坏理论时间复杂度为O(N^2)，但在实际运行中快速排序的速度较其他排序快很多，而且利用段长度小于3时用选择排序的话，验证速度提高10%~20%左右，但对于百万级的数据来说，普通的快速排序已然足够。
修改如下:
//---------------------------------------------------------------------------
#include
using namespace std;
void quick(int a[],int b,int e)
{
int i(b),j(e);
int x=a[(b+e)/2],t;
do{
while((a[i]<x)&& (i<j))//从左扫描大于中值的数
i++;
while((a[j]>x) && (j>i))//从右扫描小于中值的数
j--;
//找到了一对值,交换
if(i<=j){
t=a[j];
a[j]=a[i];
a[i]=t;
i++;
j--;
}
}while(i<=j);//如果两边扫描的下标交错，就停止（完成一次）
//当左边部分有值(b<j)，递归左半边
if(b<j){
quick(a,b,j);
}
//当右边部分有值(e>i)，递归右半边
if(e>i){
quick(a,i,e);
}
}
int main()
{
int a[10];
a[0]=7;
a[1]=5;
a[2]=8;
a[3]=2;
a[4]=6;
a[5]=9;
a[6]=2;
a[7]=5;
a[8]=6;
a[9]=1;
quick(a,0,9);
for(int i=0;i<10;i++){cout<<a[i]<<' ';}
system("pause");
}
//---------------------------------------------------------------------------
#include <iostream>
using namespace std;
typedef struct LStudent {
string id;
string name;
float math;
float chinese;
float english;
float aver;
} Str_Stu;
typedef struct LNode {
Str_Stu data;
struct LNode *next;
}LNode, *pLinkList;
enum SortType {__Math = 0, __Chinese, __English};
class student {
// 为了方便编写代码先把成员变量设置为public
public:
pLinkList m_pList;
int m_listLength;
};
inline void swap(Str_Stu **pp, int k, int j)
{
Str_Stu *temp;
temp = pp[k];
pp[k] = pp[j];
pp[j] = temp;
}
void qsort(Str_Stu **pp, int left, int right, SortType st)
{
int j, last;
if (left >= right)
return;
swap(pp, left, (left + right)/2);
last=left;
for (j = left+1; j <= right; j++)
{
if (st == __Math && pp[j]->math > pp[left]->math)
swap(pp, ++last, j);
else if (st == __Chinese && pp[j]->chinese > pp[left]->chinese)
swap(pp, ++last, j);
else if (st == __English && pp[j]->english > pp[left]->english)
swap(pp, ++last, j);
}
swap(pp, left, last);
qsort(pp, left, last-1, st);
qsort(pp, last+1, right, st);
}
void main()
{
student ss;
pLinkList cursor;
Str_Stu **pp;
int i =0;
// do something here
pp = new Str_Stu *[ss.m_listLength];
cursor = ss.m_pList;
while (cursor)
{
pp[i] = &cursor->data;
cursor = cursor->next;
}
qsort(pp, 0, ss.m_listLength-1, __Math);
for (i = 0; i < ss.m_listLength; ++i)
{
// output the sorted data here
}
qsort(pp, 0, ss.m_listLength-1, __Chinese);
for (i = 0; i < ss.m_listLength; ++i)
{
// output the sorted data here
}
qsort(pp, 0, ss.m_listLength-1, __English);
for (i = 0; i < ss.m_listLength; ++i)
{
// output the sorted data here
}
delete[] pp;
}
写一个函数
形参是指针数组 指向各个结点 再对形参指针数组排序
不影响原链表.
ypedef struct LNode {
Str_Stu data;
struct LNode *next;
}LNode, *pLinkList;
是不是应该改为
ypedef struct LNode {
LStudent data; \\Here!
struct LNode *next;
}LNode, *pLinkList;
楼主注意：快速排序是不稳定的(只能保证按主值有序，原先aver序会乱)，如果硬是要
求稳定（排序后仍然按aver有序），则严重影响排序性能。也就不能说是快速排序了。推荐使用归并排序（STL中也是这样做的）。
确定要用快速排序吗？
快速排序：
void QuickSort(int list[],int head,int tail){
if (head>=tail)return;
int left,right,temp;
temp=list[head];
left=head;right=tail;
while(left!=right){
for(;(list[right]>=temp)&&(right>left);right--); //right指针左移
if(left==right)break;
list[left++]=list[right];
for(;(list[left]<=temp)&&(left<right);left++); //left指针右移
if(left==right)break;
list[right--]=list[left];
}
list[left]=temp;
QuickSort(list,head,left-1);
QuickSort(list,right+1,tail);
}
什么？
这是哪国语？
wuyu
