八大排序算法总结+例题练习(正在不断补充...)

#include <iostream>
using namespace std;
#define Maxsize 100
void StraightInsertSort(int r[],int n) { //直接插入排序
  int i,j;
  for(i=2; i<=n; i++) //r[i]插入有序子表
    if(r[i]<r[i-1]) { //r[i]和前一个元素r[i-1]比较 如果 大于则直接下一个.该元素已有序.
      r[0]=r[i];      //r[i]暂存到r[0]中，r[0]有监视哨的作用
      r[i]=r[i-1];      //r[i-1]后移一位
      for(j=i-2; r[j]>r[0]; j--) //从后向前寻找插入位置,逐个后移，直到找到插入位置
        r[j+1]=r[j];    //r[j]后移一位
      r[j+1]=r[0];    //将r[0]插入到r[j+1]位置
    }
}
int main() {
  int i,n,r[Maxsize+1];
  cout<<"请输入数列中的元素个数n为："<<endl;
  cin>>n;
  cout<<"请依次输入数列中的元素："<<endl;
  for(i=1; i<=n; i++)
    cin>>r[i];
  StraightInsertSort(r,n);
  cout<<"直接插入排序结果："<<endl;
  for(i=1; i<=n; i++)
    cout<<r[i]<<" ";
  return 0;
}

#include<iostream>
#include<algorithm>
using namespace std;
int arr[10000+5],n;
void InsertSort(int r[],int n){//插入排序 
  int i,j;
  for(i = 2;i<=n;i++){//从第2个开始进行排序. 
    //arr[0] = r[i+1];
    if(r[i]<r[i-1]){//r[i]和前一个元素进行比较 
      arr[0]=r[i];
      r[i]=r[i-1];//r[i-1]后移一位 
      for(j=i-2;r[0]<r[j];j--){
        r[j+1]=r[j];//当前元素后移  如果 r[0]<r[j]
      }
      r[j+1]=r[0];//将r[0]存入r[j+1] 
    } 
  } 
} 
int main()
{
  cin>>n;
  for(int i = 1;i<=n;i++){
    cin>>arr[i];
  }
  //sort(arr+1,arr+1+n);
  InsertSort(arr,n);
  cout<<arr[n/2+1]<<endl;
  return 0;
}

#include <iostream>
using namespace std;
#define Maxsize 100
void BubbleSort(int r[],int n) //冒泡排序
{
    int i,j,temp;
    bool flag;
    i=n-1;
    flag=true;
    while(i>0&&flag)//当flag为false说明该轮排序已无交换,排序结束. 
    {
        flag=false;
        for(j=0;j<i;j++) //进行一趟排序
            if(r[j]>r[j+1])
            {
                flag=true;
                temp=r[j]; //交换两个记录
                r[j]=r[j+1];
                r[j+1]=temp;
            }
        for(j=0;j<=i;j++)//测试每趟排序结果
            cout<<r[j]<<" ";
        cout<<endl;
        i--;
    }
}
int main()
{
    int i,n,r[Maxsize];
    cout<<"请输入数列中的元素个数n为："<<endl;
    cin>>n;
    cout<<"请依次输入数列中的元素："<<endl;
    for(i=0;i<n;i++)
       cin>>r[i];
    BubbleSort(r,n);
    cout<<"冒泡排序结果："<<endl;
    for(i=0;i<n;i++)
       cout<<r[i]<<" ";
    return 0;
}

#include<iostream>
#include<ctime>
#include<cstdlib>
using namespace std;
int Partition(int r[],int low,int high) { //划分函数
  int i = low,j=high,pivot=r[low];//基准元素
  while(i<j) {
    while(i<j&&r[j]>pivot)
      j--;//向左扫描
    if(i<j) {
      swap(r[i++],r[j]);//r[i]和r[j]交换后i+1后移一位
    }
    while(i<j&&r[i]<=pivot)
      i++;//向右扫描
    if(i<j) {
      swap(r[i],r[j--]);//r[i]和r[j]交换后 j-1左移一位
    }
  }
  return i;//返回最终划分完成后基准元素所在的位置
}
int Partition2(int r[],int low,int high) { //划分函数
  k = (rand()%(high-low+1))+low;//产生一个随机基准元素.. 
  swap(r[low],r[k]); // 将基准元素和第一个元素进行交换,就依旧可以使用之前的代码了.. 
  int i = low,j=high,pivot=r[low];//基准元素
  while(i<j) {
    while(i<j&&r[j]>pivot)//想左扫描  直到 r[j] >= pivot   因为咱们是从右边往左找比基准<=的元素，从左边往右找比基准>的元素，所以标准元素位置在扫描过程中会保持不变.
      j--;
    while(i<j&&r[i]<=pivot) { //向右扫描 知道 r[i] < pivot 为啥这个可以有等号呢？
      i++;
    }
    if(i<j) {
      swap(r[i++],r[j--]);//r[i]和r[j]交换
    }
  }
  if(r[i]>pivot) { //r[i]如果比标准元素大
    swap(r[i-1],r[low]);//r[i-1]和r[low]交换
    return i-1;//返回最终划分完成后基准元素所在的位置.
  }
  swap(r[i],r[low]);//r[i]和r[low]交换
  return i;// 返回最终划分完成后基准元素所在的位置.
}
void QuickSort(int R[],int low,int high) { //实现快排算法
  int mid;
  if(low<high) {
    mid=Partition2(R,low,high);//基准位置
    QuickSort(R,low,mid-1);//左区间递归快排
    QuickSort(R,mid+1,high); //右区间递归快排
  }
}
int main() {
  int a[100];
  int i,n;
  cout<<"请先输入要排序的数据的个数:";
  cin>>n;
  cout<<"请输入要排序的数据:";
  for(int i = 0; i<n; i++) {
    cin>>a[i];
  }
  cout<<endl;
  QuickSort(a,0,n-1);
  cout<<"排序后的序列为:"<<endl;
  for(int i = 0; i<n; i++) {
    cout<<a[i]<<" ";
  }
  cout<<endl;
  return 0;
}

#include<iostream>
using namespace std;
void Merge(int A[], int low,int mid,int high){//合并函数 
  int *B = new int[high-low+1];//申请一个辅助数组 
  int i = low,j=mid+1,k=0;
  while(i<=mid && j<= high){//按从小到大存放辅助数组B[]中
    if(A[i] <= A[j]){
      B[k++]=A[i++];//如果i所指的元素小,将其放入B后,i,k后移. 
    }else{
      B[k++]=A[j++];//如果j所指的元素小,将其放入B后,j,k后移.
    } 
  }
  while(i<=mid){//如果i所指的数组中元素未放完. 
    B[k++]=A[i++];//将数组剩下的元素放到B中 
  } 
  while(j<=high){
    B[k++]=A[j++]; 
  }
  for(i = low,k = 0;i<=high;i++){//将排好序的元素重新放回A 因为后序可能会和其他的进行合并排序.. 
    A[i]=B[k++];
  }
  delete []B; 
}
void MergeSort(int A[],int low,int high){//合并排序 
  if(low<high){
    int mid=(low+high)/2;//取中点
    MergeSort(A,low,mid);//对A[low:mid]中的元素合并排序
    MergeSort(A,mid+1,high);//对A[mid+1:high]中的元素合并排序
    Merge(A,low,mid,high);//合并 
  }
} 
int main()
{
  int n,A[100];
  cout<<"请输入队列中的元素个数n为:"<<endl;
  cin>>n;
  cout<<"请依次输入数列中的元素:"<<endl;
  for(int i = 0;i < n;i++){
    cin>>A[i];
  } 
  MergeSort(A,0,n-1);
  cout<<"合并排序结果:"<<endl;
  for(int i = 0;i < n;i++){
    cout<<A[i]<<" ";
  } 
  cout<<endl;
  return 0;
 }