算法设计常用的四种排序

吉林农业大学算法设计与分析

四种排序方法：

一、选择排序：

1. 初始化一个长度为r[]的数组；

1.1数组下标从1开始； 2. for（i=1;i<=n-1:i++）

2.1 for(j=i+1;j<=n:j++) 2.2 在无序区中找最小记录； 2.3 若最小记录不在最终位置则交换； 二、起泡排序：

1.初始化一个长度为r[]的数组；

1.1数组下标从1开始； 2.for(i=1;i<=n-1;i++) 2.1 for(j=1;j<=n-i;j++) 2.2如果反序，则交换元素； 三、 归并排序：

1.初始化一个长度为r[]的数组； 2.若s==t则r1[s]=r[s]; 2.1 m=(s+t)/2;

2.2 归并排序前半子序列； 2.3 归并排序后半子序列； 2.4 合并两个已排序的子序列；

信息技术学院信息与计算科学Jackiedc

吉林农业大学算法设计与分析

四、快速排序：

1.初始化一个长度为r[]的数组； 2.若开始小于结尾

2.1问题分解，pivot是轴值在序列序列中的位置； 2.2递归地对左侧子序列进行快速排序； 2.3递归地对右侧子序列进行快速排序；

#include using namespace std;

void SelectSort(int r[],int n);

void swap(int& a ,int& b); //交换排序 void BubbleSort(int r[],int n); //起泡排序 void MergeSort(int r[],int r1[],int s,int t); //归并排序

void Merge(int r[],int r1[],int s,int m,int t); //合并有序子序列 void MergeSort(int r[],int r1[],int s,int t); //归并排序 int Partition(int r[],int first,int end); //一次划分 void QuickSort(int r[],int first,int end); //快速排序 int count=0; int number=0; int main() { int r[12]={9,78,25,23,4,68,75,30,26,44,20,33}; int r1[12];

SelectSort(r,12); cout<<\选择排序：\ for(int i(0);i<12;i++) cout<

BubbleSort(r,12); cout<<\起泡排序：\ for(int j(0);j<12;j++) cout<

MergeSort(r,r1,0,11); cout<<\归并排序运行次数:\

信息技术学院信息与计算科学Jackiedc

吉林农业大学算法设计与分析

cout<<\归并排序：\ for(int q=0;q<12;q++) cout<

QuickSort(r,0,11); cout<<\快速排序运行次数:\ cout<<\快速排序：\ for(int d=0;d<12;d++) cout<

void SelectSort(int r[],int n)//选择排序 { int count=0; int index=0; for(int i=0;i<=n-1;i++) { index=i; for(int j=i+1;j<=n;j++){ if(r[j]

void swap(int& a ,int& b)//交换 { int c=0; c=a; a=b; b=c; }

void BubbleSort(int r[],int n)//起泡排序 { int count=0;

for(int i=1;i<=n-1;i++) for(int j=1;j<=n-i;j++) { if(r[j]>r[j+1]) swap(r[j],r[j+1]); count++; }

信息技术学院信息与计算科学Jackiedc

吉林农业大学算法设计与分析

cout<<\起泡排序运行次数：\}

void MergeSort(int r[],int r1[],int s,int t)//归并排序 { count++; int m=0;int count=0; if(s==t) r1[s]=r[s]; else { m=(s+t)/2; MergeSort(r,r1,s,m); MergeSort(r,r1,m+1,t); Merge(r1,r,s,m,t); count++; } //cout<<\归并排序运行次数：\ }

void Merge(int r[],int r1[],int s,int m,int t)//合并有序子序列 { int i;int j;int k; i=s;j=m+1;k=s; while(i<=m&&j<=t) { if(r[i]<=r[j]) r1[k++]=r[i++]; else r1[k++]=r[j++]; } if(i<=m) while(i<=m) r1[k++]=r[i++]; else while(j<=t) { r1[k++]=r[j++]; } for(int l=0;l<12;l++) r[l]=r1[l]; }

int Partition(int r[],int first,int end)//一次划分 {

int i;int j; i=first;j=end; //初始化 while(i

信息技术学院信息与计算科学Jackiedc

吉林农业大学算法设计与分析

{ while(i

void QuickSort(int r[],int first,int end)//快速排序 { number++; int pivot; if(first

信息技术学院信息与计算科学Jackiedc

本文来源：https://www.bwwdw.com/article/xpz2.html