直接插入排序
#include<stdio.h>
#include<iostream>
using namespace std;
//直接插入排序（非递减）
void InsertSort(int A[],int n){
int i,j,temp;
for(i=1;i<n;i++){//从数组第二个元素开始比较
if(A[i]<A[i-1]){
temp=A[i];
for(j=i-1;j>=0&&A[j]>temp;j--){//移动元素
A[j+1]=A[j];
}
A[j+1]=temp;
}
}
}
int main(){
int A[10]={54,78,35,12,99,3,65,44,32,27};
int n=sizeof(A)/sizeof(A[0]);//数组长度
for(int i=0;i<n;i++){
cout<<"\t"<<A[i];
}
cout<<endl;
InsertSort(A,n);
for(int j=0;j<n;j++){
cout<<"\t"<<A[j];
}
cout<<endl;
return 0;
}
折半插入排序
#include<stdio.h>
#include<iostream>
using namespace std;
//折半插入排序（非递减）
void InsertSort(int A[],int n){
int i,j,temp;
int low,high,mid;
for(i=1;i<n;i++){//从数组第二个元素开始比较
temp=A[i];
low=0;
high=i-1;
while(low<=high){//查找插入的位置
mid=(low+high)/2;
if(A[mid]>temp){//左半子表
high=mid-1;
}
else{//右半子表
/*此处和折半查找有区别，当mid所处的元素小于或等于temp时，保证算法的稳定性
比如 50,54,60,60，60，60,87； 60所处位置后面有多个60，保证稳定性*/
low=mid+1;
}
}
for(j=i-1;j>=0&&j>=high+1;j--){//退出时要插入的位置在high后面，查找要插入的位置，然后移动元素
A[j+1]=A[j];
}
A[high+1]=temp;
}
}
int main(){
int A[10]={47,78,50,12,99,3,6,44,32,27};
int n=sizeof(A)/sizeof(A[0]);//数组长度
for(int i=0;i<n;i++){
cout<<"\t"<<A[i];
}
cout<<endl;
InsertSort(A,n);
for(int j=0;j<n;j++){
cout<<"\t"<<A[j];
}
cout<<endl;
return 0;
}
直接插入排序演示
希尔排序
#include<stdio.h>
#include<iostream>
using namespace std;
//希尔排序
void ShellSort(int A[],int n){
int d,i,j;
for(d=n/2;d>=1;d=d/2){//步长的变化
for(i=1+d;i<=n;++i){//进入当前步长的子表进行直接插入排序，每次处理子表的一个元素(++i)
if(A[i]<A[i-d]){//子表判断
//A[0]作为暂存当前比较元素的单元，并不是“哨兵”
A[0]=A[i];
for(j=i-d;j>0&&A[0]<A[j];j=j-d){//寻找子表的插入位置，元素后移
A[j+d]=A[j];
}
A[j+d]=A[0];
}
}
}
}
int main(){
int A[15]={0,44,25,61,47,17,78,50,12,99,3,6,44,32,27};
int n=14;//比较的元素个数
for(int i=1;i<=n;i++){
cout<<"\t"<<A[i];
}
cout<<endl;
ShellSort(A,n);
cout<<"希尔排序"<<endl;
for(int j=1;j<=n;j++){
cout<<"\t"<<A[j];
}
cout<<endl;
return 0;
}
希尔排序演示
冒泡排序
#include<stdio.h>
#include<iostream>
using namespace std;
//交换两个元素位置
void swap(int &a,int &b){
int temp;
temp=a;
a=b;
b=temp;
}
//冒泡排序
void BubbleSort(int A[],int n){
bool flag=false;
for(int i=n-2;i>=0;i--){//n个元素需要n-1此比较
flag=false;//标志位：在一次冒泡过程中是否进行了元素交换
for(int j=0;j<=i;j++){//每次比较冒出最大的元素，排在后面，
//只需要比较到有序部分的前面一个元素
if(A[j]>A[j+1]){
swap(A[j],A[j+1]);
flag=true;
}
}
if(flag==false){//冒泡过程没有进行交换元素，说明已经有序
return;
}
}
}
int main(){
int A[10]={45,25,86,78,91,3,65,14,36,55};
int n=sizeof(A)/sizeof(A[0]);//数组长度
for(int i=0;i<n;i++){
cout<<"\t"<<A[i];
}
cout<<endl;
BubbleSort(A,n);
cout<<"冒泡排序"<<endl;
for(int j=0;j<n;j++){
cout<<"\t"<<A[j];
}
cout<<endl;
return 0;
}
冒泡排序演示
快速排序
#include<stdio.h>
#include<iostream>
using namespace std;
//用第一个元素将数组划分为两个部分
int Partition(int A[],int low,int high){
int pivot=A[low];//取表的第一个元素作为枢轴
while(low<high){
while(low<high&&A[high]>pivot){//从后往前找到high所指元素小于枢轴的元素
high--;
}
A[low]=A[high];//将找到的元素赋值给low所指位置
while(low<high&&A[low]<pivot){//从前往后找到low所指元素大于枢轴的元素
low++;
}
A[high]=A[low];//将找到的元素赋值给high所指位置
}
A[low]=pivot;//退出循环时low等于high，将枢轴元素赋值到low所指位置
//此时枢轴左边的元素小于枢轴，右边的大于枢轴
return low;
}
//快速排序
void QuickSort(int A[],int low,int high){
if(low<high){
int pivotposition=Partition(A,low,high);//划分数组
QuickSort(A,low,pivotposition-1);//快速排序左表
QuickSort(A,pivotposition+1,high);//右表快排
}
}
int main(){
int A[12]={15,27,86,71,91,3,65,14,49,98,36,55};
int n=sizeof(A)/sizeof(A[0]);//数组长度
for(int i=0;i<n;i++){
cout<<"\t"<<A[i];
}
cout<<endl;
QuickSort(A,0,n-1);
cout<<"快速排序"<<endl;
for(int j=0;j<n;j++){
cout<<"\t"<<A[j];
}
cout<<endl;
return 0;
}
快速排序演示
简单选择排序
#include<stdio.h>
#include<iostream>
using namespace std;
//交换两个元素位置
void swap(int &a,int &b){
int temp;
temp=a;
a=b;
b=temp;
}
//简单选择排序
void SelectionSort(int A[],int n){
for(int i=0;i<n-1;i++){//总共需要进行n-1次寻找最小值
int min=i;
for(int j=i+1;j<n;j++){//寻找最小值
if(A[j]<A[min]){
min=j;
}
}
if(min!=i){//最小值放在前面，递增有序
swap(A[min],A[i]);
}
}
}
int main(){
int A[12]={14,24,86,71,88,5,65,14,49,97,36,55};
int n=sizeof(A)/sizeof(A[0]);//数组长度
for(int i=0;i<n;i++){
cout<<"\t"<<A[i];
}
cout<<endl;
SelectionSort(A,n);
cout<<"简单选择排序"<<endl;
for(int j=0;j<n;j++){
cout<<"\t"<<A[j];
}
cout<<endl;
return 0;
}
简单选择排序演示