c++快速排序算法代码

1．将i 和j分别指向待排序区域的最左侧记录和最右侧记录的位置；

2．重复下述过程，直到i=j

21右侧扫描，直到记录j的关键码小于基准记录的关键码；

22 如果i<j，则将r[j]与r[i]交换，并将i++；

23左侧扫描，直到记录i的关键码大于基准记录的关键码；

24 如果i<j，则将r[i]与r[j]交换，并将j--；

3．退出循环，说明i和j指向了基准记录所在位置，返回该位置；

void QuickSort(int r[ ], int first, int end)

{

if (first<end) { //递归结束

pivot=Partition(r, first, end); //一次划分

QuickSort(r, first, pivot-1); //递归地对左侧子序列进行快速排序

QuickSort(r, pivot+1, end); //递归地对右侧子序列进行快速排序

}

}

int Partition(int r[ ], int first, int end)

{

i=first; j=end; //初始化

while (i<j)

{

while (i<j && r[i]<= r[j]) j--； //右侧扫描

if (i<j) {

r[i]←→r[j]; //将较小记录交换到前面

i++;

}

while (i<j && r[i]<= r[j]) i++； //左侧扫描

if (i<j) {

r[j]←→r[i]; //将较大记录交换到后面

j--;

}

}

retutn i; //i为轴值记录的最终位置

}

这题你只要把每个算法的程序代码看一下，在计算下就行

冒泡排序：两个循环，从1加到N，(1+N)N/2 = 500500,最坏交换情况是每次判断都要交换，既5005003次

选择排序：也是两个循环，比较次数跟冒泡排序一样500500，但是这个只要底层循环交换，既只需10003 = 3000次赋值。

插入排序：循环次数一样500500，但是这个最坏情况是每比较一次就赋值一次，既需500500次赋值

希尔排序：时间复杂度是N^13倍，比较次数和赋值应该是1000^13次方。

归并排序和快速排序，你去查查它的时间复杂度是怎么算，O(lgNN),好像有系数，算法导论那本书上有，现在不记得是多少了。

希望能帮到你，

#include<stdioh>

#include<malloch>

#include<conioh>

typedef struct VNode

{

int info;

struct VNode next_node;

}Node;

void input(Nodehead, int number)

{

if(number!=0)

{

int i;

Node t;

t=(Node )malloc(sizeof(Node));

head->next_node=t;

scanf("%d",&i);

t->info=i;

input(t,number-1);

}

}

void output(Nodehead, int count)

{

Node t;

if(count!=0)

{

t=head->next_node;

printf("%d ",t->info);

output(t,count-1);

}

}

void select(Nodehead, int num)

{

int tem=0;

if(num!=0)

{

int min_node;

Node t;

Node r;

Node q;

t=head->next_node;

r= head->next_node;

q=head;

min_node= t->info;

for(int i=0;i<num;i++)

{

if(min_node>t->info)

{

min_node= t->info;

r=t;

tem=i;

}

t=t->next_node;

}

for(int j=0;j<tem;j++)

q=q->next_node;

q->next_node=r->next_node;

r->next_node=head->next_node;

head->next_node=r;

select(head->next_node,num-1);

}

}

int main()

{

int num;

Node head;

head=( Node )malloc(sizeof(Node));

printf("请输入序列数据的个数：");

scanf("%d",&num);

printf("请输入序列的数据：\n");

input(head,num);

printf("\n选择排序后的序列为：\n");

select(head,num);

output(head,num);

getch();}

选择排序法：

public class TSort{

public static void main(String args[]){

int a[]={12,45,2,5,26,56};

for(int i=0;i<alength-1;i++){

int t;

for(int j=i+1;j<alength;j++){

if(a[i]>a[j]){

t=a[i];a[i]=a[j];a[j]=t;

}

}

}

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

Systemoutprint(a[i]+" ");

}

}

}

#include<stdioh>

void main(){

int i,j,score[10],count=0,temp,sum=0;

double avg;

for(i=0;i<10;i++){ //输入10个学生的成绩，并求着10个学生的成绩总和

printf("请输入第%d个学生的成绩：",(i+1));

scanf("%d",&score[i]);

sum+=score[i];

}

avg=sum10/10; //求着这10个学生成绩的平均值

for(i=0;i<10;i++){ //统计小于平均分的学生人数

if(score[i]<avg){

count++;

}

}

for(i=0;i<10;i++){ //使用冒泡排序对这10个学生的成绩逆序排序

for(j=0;j<9-i;j++){

if(score[j]<score[j+1]){

temp=score[j];

score[j]=score[j+1];

score[j+1]=temp;

}

}

}

printf("最高成绩：%d分，平均成绩：%2f分,低于平均成绩的人数是：%d人!\n",score[0],avg,count);

}

下面是我以前写的，希望对你有帮助。

#include<iostream>

#include<cstdlib>

#include<ctime>

using namespace std;

#define N 100 //产生的数的个数

//冒泡排序

void Bubble_Sort(int R[],int n ){

char flag='0';

cout<<"是否输出所有的数字(1/0):"<<endl;

cin>>flag;

while(flag>'1'||flag<'0'){

cout<<"输入有误，请重新输入:"<<endl;

cin>>flag;

}

int i;

if(flag=='1'){

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

for( i=1;i<=n;i++)

cout<<R[i]<<',';

cout<<endl;

}

for(i=1;i<n;i++){ //执行n-1趟

int swap=0;

for(int j=1;j<=n-i;j++){

if(R[j] > R[j+1] ){

R[0]=R[j];

R[j]=R[j+1];

R[j+1]=R[0];

swap=1;

}

}

if(swap==0) // 没有发生一次交换，说明序列有序，则跳出循环，排序结束

break;

}

if(flag=='1'){

cout<<"冒泡排序后:"<<endl;

for(i=1;i<=n;i++)

cout<<R[i]<<',';

cout<<endl;

}

}

//快速排序

int Partition(int R[],int i,int j){ //已R[i]为支点进行划分，算法返回支点记录最终的位置

R[0]=R[i]; //缓存支点记录

while(i<j){ //从表的两端交替地向中间扫描

while(i<j&&R[j]>=R[0])

j--;

if(i<j){ //将比支点记录小的交换到前面

R[i]=R[j];

i++;

}

while(i<j&&R[i]<R[0])

i++;

if(i<j){ //将比支点记录大的交换到后面

R[j]=R[i];

j--;

}

}

R[i]=R[0];

return i;

}

void Quick_Sort(int R[],int s,int t){

int i;

if(s<t){

i=Partition(R,s,t); //将表一分为二

Quick_Sort(R,s,i-1); //对支点前端子表递归排序

Quick_Sort(R,i+1,t); //对支点后端子表递归排序

}

}

void Quick(int R[],int n){

char flag='0';

cout<<"是否输出所有的数字(1/0):"<<endl;

cin>>flag;

while(flag>'1'||flag<'0'){

cout<<"输入有误，请重新输入:"<<endl;

cin>>flag;

}

int i;

if(flag=='1'){

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

for(i=1;i<=n;i++)

cout<<R[i]<<',';

cout<<endl;

}

Quick_Sort(R,1,n);

if(flag=='1'){

cout<<"快速排序后:"<<endl;

for(i=1;i<=n;i++)

cout<<R[i]<<',';

cout<<endl;

}

}

int main(){

while(1){

int R[N+1],i;

cout<<"1 在完全随机的情况下对关键码进行排序"<<endl;

cout<<"2 在完全正序的情况下对关键码进行排序"<<endl;

cout<<"3 在完全逆序的情况下对关键码进行排序"<<endl;

cout<<"0 退出"<<endl;

cout<<"请选择:"<<endl;

char p;

cin>>p;

while(p-48<0||p-48>3){

cout<<"输入有误，请重新输入:"<<endl;

cin>>p;

}

if(p-48==0)

break;

if(p-48==1){

srand((unsigned)time(NULL));

for(i=1;i<=N;i++)

R[i]=rand()%10000+1;

}

else if(p-48==2){

for(i=1;i<=N;i++)

R[i]=i;

}

else

for(i=N;i>=1;i--)

R[N-i+1]=i;

char k;

cout<<endl;

cout<<"1 冒泡排序"<<endl;

cout<<"2 快速排序"<<endl;

cout<<"0 退出"<<endl;

cout<<"请选择排序方法:"<<endl;

cin>>k;

while(k-48<0||k-48>2){

cout<<"输入有误，请重新输入:"<<endl;

cin>>k;

}

switch(k-48){

case 0:cout<<"谢谢使用!"<<endl;exit(0);

case 1:Bubble_Sort(R,N);break;

case 2:Quick(R,N);break;

}

system("pause");system("cls");

}

return 0;

}

对于非科班生的我来说，算法似乎对我来说是个难点，查阅了一些资料，趁此来了解一下几种排序算法。

首先了解一下，什么是程序

关于排序算法通常我们所说的往往指的是内部排序算法，即数据记录在内存中进行排序。

排序算法大体可分为两种：

一种是比较排序，时间复杂度O(nlogn) ~ O(n^2)，主要有：冒泡排序，选择排序，插入排序，归并排序，堆排序，快速排序等。

另一种是非比较排序，时间复杂度可以达到O(n)，主要有：计数排序，基数排序，桶排序等

冒泡排序它重复地走访过要排序的元素，一次比较相邻两个元素，如果他们的顺序错误就把他们调换过来，直到没有元素再需要交换，排序完成。这个算法的名字由来是因为越小(或越大)的元素会经由交换慢慢“浮”到数列的顶端。

选择排序类似于冒泡排序，只不过选择排序是首先在未排序的序列中找到最小值（最大值），放到序列的起始位置，然后再从剩余未排序元素中继续寻找最小（大）元素，放到已排序序列的末尾，以此类推，直到所有元素均排序完毕。

插入排序比冒泡排序和选择排序更有效率，插入排序类似于生活中抓扑克牌来。

插入排序具体算法描述，以数组[3, 2, 4, 5, 1]为例。

前面三种排序算法只有教学价值，因为效率低，很少实际使用。归并排序（Merge sort）则是一种被广泛使用的排序方法。

它的基本思想是，将两个已经排序的数组合并，要比从头开始排序所有元素来得快。因此，可以将数组拆开，分成n个只有一个元素的数组，然后不断地两两合并，直到全部排序完成。

以对数组[3, 2, 4, 5, 1] 进行从小到大排序为例，步骤如下：

有了merge函数，就可以对任意数组排序了。基本方法是将数组不断地拆成两半，直到每一半只包含零个元素或一个元素为止，然后就用merge函数，将拆成两半的数组不断合并，直到合并成一整个排序完成的数组。

快速排序（quick sort）是公认最快的排序算法之一，有着广泛的应用。

快速排序算法步骤

参考：

常用排序算法总结(一)

阮一峰-算法总结

以上就是关于c++快速排序算法代码全部的内容，包括:c++快速排序算法代码、排序算法性能比较（数据结构）C语言程序、设计一个用链表表示的直接选择排序算法，并用程序实现等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！