撕烂数据爆锤算法：内排序之交换算法

前言：
小鑫鑫课堂开课了，孩子数据结构老差了，多半是废了，快看撕烂数据爆锤算法系列吧…撕烂数据，爆锤算法，这是你的不二选择。（请允许我的厚颜无耻，正所谓黄婆卖瓜自卖自夸嘛！）今天记录的是我在学习交换排序中一些小小总结，希望对你有所帮助啦。总之，码字不易，还望各位多多支持哦！
同是天涯码字猿，
共勉，共勉~~~

正文：

一、基础概述：

a.冒泡排序：从左向右扫描一个序列，只要发现两个相邻的数据元素处于逆序，则交换这两个元素的位置。以升序为例，所谓的逆序状态是指Date[i]>Date[i+1]的状态，正序是指date[i]<=Date[i+1]的状态。这样扫描一遍，被称为一趟冒泡。每趟冒泡之后，序列中的最大元素一定位于序列最后。接下来忽略这个最大元素，对剩余的部分再进行一趟冒泡。这样重复冒泡直到剩余的序列长度为1为止。长度为N的序列，最多需要N-1趟冒泡。

b.冒泡排序的改进：记下最后一次交换操作的位置flag，下次冒泡区间是Date[0…flag]而不是Date[0…n-i]。用传送代替交换。传送操作在遇到需要连续交换的情况下，会有效的减少数据移动的量。以Date[i+1],Date[i+2],Date[i+3]连续交换为例，所谓传送是指首先用temp保存Date[i]，然后将Date[i+1],Date[i+2],Date[i+3]依次向左移动一个单元，最后将temp复制到Date[i+3]上。在两个方向上对序列进行冒泡，压缩冒泡区间。

c.快速排序：是对冒泡法排序的一种改进。快速排序算法的基本思想是：将所要进行排序的数分为左右两个部分，其中一部分的所有数据都比另外一 部分的数据小，然后将所分得的两部分数据进行同样的划分，重复执行以上的划分操作，直 到所有要进行排序的数据变为有序为止。

二、时间（或空间）复杂度：

a.冒泡排序：最坏情况和平均时间复杂度是O(n^2)，最好情况下的时间复杂度为O(n)。

b.快速排序：理想情况下时间复杂度为O(N*log(2)N)，最坏情况下时间复杂度为O(n^2)。

三、代码实现：

一、直接插入排序

1.定义头文件：

#include<stdio.h>
#define MAXSIZE 100
void TraverseDate(int Date[],int n);         //遍历元素
void InitDate(int Date[],int &n);            //初始化待排元素
void SortDate(int Date[],int n);             //简单冒泡排序
int main();                                  //主函数

2.遍历元素：

void TraverseDate(int Date[],int n)           //遍历元素
{
 int i;
 for(i=1;i<=n;i++)
  printf("%4d",Date[i]);
 putchar(10);
    putchar(10);
 return;
}

3.初始化待排元素：

void InitDate(int Date[],int &n)           //初始化待排元素
{
 int i;
 printf("\n请输入待排元素个数:");
 scanf("%d",&n);
 putchar(10);
 for(i=1;i<=n;i++)
 {
  printf("\n请输入待排元素:");
  scanf("%d",&Date[i]);
 }
 putchar(10);
 printf("\n待排元素为:");
 TraverseDate(Date,n);
 return;
}

4.冒泡排序（核心）：

void SortDate(int Date[],int n)           //冒泡排序
{
 int i,j,t,flag;
 for(i=1;i<=n;i++)                     
 {
  flag=1;                           //flag作为标志，用来判断经过一趟交换后，序列是否变为有序
  for(j=1;j<=n-i;j++)    //因为每一趟得到一个较前面元素大的元素，交换至每一趟的末位，故末位序列元素已经有序，不用进行比较
  {
   if(Date[j]>Date[j+1])         //相邻两元素进行比较，若前一元素大于后一元素，两元素进行交换
   {
    t=Date[j];
    Date[j]=Date[j+1];
    Date[j+1]=t;
    flag=0;
   }
  }
  if(flag==1)
   break;
 }
 printf("\n排序结果为:");
 TraverseDate(Date,n);
 return;
}

5.主函数：

int main()                                   //主函数
{
 int n,Date[MAXSIZE];
 InitDate(Date,n);
 SortDate(Date,n);
 return 0;
}

6.运行结果：

二、冒泡排序的改进

1.定义头文件：

#include<stdio.h>
#define MAXSIZE 100
void TraverseDate(int Date[],int n);         //遍历元素
void InitDate(int Date[],int &n);            //初始化待排元素
void Sort(int Date[],int n);                  //冒泡排序
void SortDate(int Date[],int n);             //冒泡排序接口
int main();                                  //主函数

2.遍历元素：

void TraverseDate(int Date[],int n)           //遍历元素
{
 int i;
 for(i=1;i<=n;i++)
  printf("%4d",Date[i]);
 putchar(10);
    putchar(10);
 return;
}

3.初始化待排元素：

void InitDate(int Date[],int &n)             //初始化待排元素
{
 int i;
 printf("\n请输入待排元素个数:");
 scanf("%d",&n);
 putchar(10);
 for(i=1;i<=n;i++)
 {
  printf("\n请输入待排元素:");
  scanf("%d",&Date[i]);
 }
 putchar(10);
 printf("\n待排元素为:");
 TraverseDate(Date,n);
 return;
}

4.冒泡排序（核心）：

void Sort(int Date[],int n)                     //冒泡排序
{
 int low,high,flag,i,j,temp;    //high,low用来标识冒泡区域
 high=n;                        //如果flag是1,表示已经有序，否则flag是一个方向冒泡区间的终点，又是另一个冒泡区间的起点
 low=1;                     
 flag=1;                        //从左向右方向上，冒泡区间初始值为1，终点是n
 while(low<high)   //从左开始冒泡 
 {                            
  low=flag;          //冒泡区间被标识为Date[low...high]
  i=low;
  flag=1;            //假定未发生交换 
  while(i<high)
  {
   if(Date[i]>Date[i+1])         //发现逆序，执行传送操作
   {
    temp=Date[i];              //保存Date[i]
    while(i<high&&temp>Date[i+1])
    {                                //将比temp小的元素向左移动
     Date[i]=Date[i+1];
     i++;
    }
    Date[i]=temp;              //将temp传送到正确的位置
    flag=i-1;                  //如果这是最后一次传送，那么flag就是新冒泡区间的终点
   }
   i++;
  }
  if(flag==1)                        //未发生交换，Date已经有序，跳出
   break;                         //开始自右往左冒泡
  high=flag;                         //设定新的冒泡起点
  j=high;
  flag=1;                            //假定未发生冒泡
  while(j>low)
  {
   if(Date[j]<Date[j-1])          //发现逆序，执行传送操作
   {
    temp=Date[j];
    while(j>low&&temp<Date[j-1]) 
    {
     Date[j]=Date[j-1];
     j--;
    }
    Date[j]=temp;
    flag=j+1;              //如果这是最后一次传送，那么flag就是新冒泡区间的起点
   } 
   j--;
  }
  if(flag==1)                    //未发生交换，Date已经有序，跳出
   break;
 }
 return;
}

5.冒泡排序接口：

void SortDate(int Date[],int n)                  //冒泡排序接口
{
 Sort(Date,n);
 printf("\n排序结果为:");
 TraverseDate(Date,n);
 return;
}

6.主函数：

int main()                                       //主函数
{
 int n,Date[MAXSIZE];
 InitDate(Date,n);
 SortDate(Date,n);
 return 0;
}

7.运行结果：

三、快速排序

1.定义头文件：

#include<stdio.h>
#define MAXSIZE 100
void TraverseDate(int Date[],int n);         //遍历元素
void InitDate(int Date[],int &n);            //初始化待排元素
void Sort(int Date[],int n);                  //快速排序
void SortDate(int Date[],int n);             //快速排序接口
int main();                                  //主函数

2.遍历元素：

void TraverseDate(int Date[],int n)          //遍历元素
{
 int i;
 for(i=1;i<=n;i++)
  printf("%4d",Date[i]);
 putchar(10);
    putchar(10);
 return;
}

3.初始化待排元素：

void InitDate(int Date[],int &n)              //初始化待排元素
{
 int i;
 printf("\n请输入待排元素个数:");
 scanf("%d",&n);
 putchar(10);
 for(i=1;i<=n;i++)
 {
  printf("\n请输入待排元素:");
  scanf("%d",&Date[i]);
 }
 putchar(10);
 printf("\n待排元素为:");
 TraverseDate(Date,n);
 return;
}

4.快速排序（核心）：

void Sort(int Date[],int left,int right)         //快速排序
{
 int i,j,temp,t;
 if(left>right)
  return;
 i=left;                           //区间起始值
 j=right;                          //区间末位值
 temp=Date[left];                  //存储选定的起始值
 while(i<j)
 {
  while(i<j&&Date[j]>=temp)      //在temp右边找到比temp小的元素1
   j--;
  while(i<j&&Date[i]<=temp)      //在temp右边找到比temp小的元素2
   i++;
  if(i<j)                        //交换元素1与元素2的位置
  {
   t=Date[i];
   Date[i]=Date[j];
   Date[j]=t;
  }
 }
 Date[left]=Date[i];                 //交换Date[left](起始值)与中间元素Date[i]位置
 Date[i]=temp;
 Sort(Date,left,i-1);                //排序i(也就是此时起始值所在)的左边部分
 Sort(Date,i+1,right);               //排序i(也就是此时起始值所在)的右边部分
 return;
}

5.快速排序接口：

void SortDate(int Date[],int n)          //快速排序接口
{
 Sort(Date,1,n);
 printf("\n排序结果为:");
 TraverseDate(Date,n);
 return;
}

6.主函数：

int main()                                //主函数
{
 int n,Date[MAXSIZE];
 InitDate(Date,n);
 SortDate(Date,n);
 return 0;
}

7.运行结果：

尾言：
看完这<撕烂数据爆锤算法：内排序之交换算法>，是否还意犹未尽，那么就跟着我进入推荐环节吧（恬不知耻的我，死活都要自荐一翻，哈哈）。
小小推荐：
撕烂数据爆锤算法系列：
撕烂数据爆锤算法：内排序之插入算法
撕烂数据爆锤算法：循环链表
撕烂数据爆锤算法：单链表

感谢浏览，你们的支持就是我的动力，下次再见喽~~~