数据结构：算法篇：快速排序；直接插入排序

目录

快速排序

直接插入排序

改良版冒泡排序

---

快速排序

理解：

①从待排序元素中选定一个基准元素；

②以基准元素将数据分为两部分：（可以将：大于基准元素放左，小于基准元素放右）

③对左半部分（从左端到基准数据）进行①②操作；直到数据有序

    即将左端到基准数据作为范围，传入；这个范围又会产生新的范围：左端到基准数据2；

    ……

    直到数据有序

④对左半部分（从基准数据到右端）进行①②操作；

【粗劣分析：便于理解】

右半部分：

【深层分析：便于代码】

遍历直倒有序：

数据有序后返回上一层

代码思路

/*

思路：

选定一个基准(默认左端):   用变量temp记录基准值;

loop:

此时左端所在下标low代表的值可以被覆盖(值已经被复制了)

从右端向左端的方向,开始与temp比较,直到遇到比temp小的数,(否则就high--左移),将这个小于temp的数(下标可假定为high')放到左边，左边下标low所在的数据上

此时右端所在下标high代表的值可以被覆盖(值已经复制到下标low代表的值内了)

从左端向左端的方向,开始与temp比较,直到遇到比temp大的数,(否则就low++后移),将这个大于temp的数(下标可假定为low')放到右边，左边下标high所在的数据上

此时左端low'下标的数据可以被覆盖，回到loop;

循环结束条件:low'后移high'前移 直到相遇，说明以基准值temp将这批数据分成两份完毕。

注意：此时大小两份虽然分类完成，但是 作为基准值的数据 还未找到位置；【基准值应该放在下标为low的位置】

看下面图理解

注意，此时应low==high并且理应必须low==high，

注意，此时下标所在位置的数据应该被覆盖，

故基准值应该放在下标为low的位置(或者下标为high，反正两值相等)

*********************************************************

《基准值临界情形图》

基准值5

x x x x 6 3 x x x

        l h     此时基准值正在与l所代表元素比较l向右移中（说明h位置是无用数据）

x x x x 6 6 x x x

        l h     l数据复制给h,轮到下标h向左移动

x x x x 6 6 x x x

        ↑       两下标重合相等，此时应该放入基准值temp(h现在是无用数据)(low左边比基准值小，high右边比基准值大)

基准值7

x x x x 6 5 x x

        l h     此时基准值正在与l所代表元素比较h向左移动中（说明l位置是无用数据）

x x x x 5 5 x x

        l h     h数据复制给l,轮到下标l向左移动(h现在是无用数据)

x x x x 5 5 x x

          ↑     两下标重合相等，此时应该放入基准值temp(h现在是无用数据)(low左边比基准值小，high右边比基准值大)

*********************************************************

*/

全部代码：

#include <stdio.h>//显示函数
void showData(int buf[],int len)
{//显示for(int i=0;i<len;i++)printf("%d ",buf[i]);printf("\n");
}//快速排序函数/*************************************************************************
函数功能:   对传入的数据进行一次快速排序（分成大于基准值和小于基准值的两部分）；
输入参数:   待排序的数组，需要排序的下标范围（左端下标、右端下标）;
返回值：    基准所在的下标
*************************************************************************/
/*
思路：
选定一个基准(默认左端):   用变量temp记录基准值;loop:
此时左端所在下标low代表的值可以被覆盖(值已经被复制了)
从右端向左端的方向,开始与temp比较,直到遇到比temp小的数,(否则就high--左移),将这个小于temp的数(下标可假定为high')放到左边，左边下标low所在的数据上此时右端所在下标high代表的值可以被覆盖(值已经复制到下标low代表的值内了)
从左端向左端的方向,开始与temp比较,直到遇到比temp大的数,(否则就low++后移),将这个大于temp的数(下标可假定为low')放到右边，左边下标high所在的数据上此时左端low'下标的数据可以被覆盖，回到loop;循环结束条件:low'后移high'前移 直到相遇，说明以基准值temp将这批数据分成两份完毕。注意：此时大小两份虽然分类完成，但是 作为基准值的数据 还未找到位置；【基准值应该放在下标为low的位置】看下面图理解
注意，此时应low==high并且理应必须low==high，
注意，此时下标所在位置的数据应该被覆盖，
故基准值应该放在下标为low的位置(或者下标为high，反正两值相等)
*********************************************************
《基准值临界情形图》
基准值5
x x x x 6 3 x x xl h     此时基准值正在与l所代表元素比较l向右移中（说明h位置是无用数据）
x x x x 6 6 x x xl h     l数据复制给h,轮到下标h向左移动
x x x x 6 6 x x x↑       两下标重合相等，此时应该放入基准值temp(h现在是无用数据)(low左边比基准值小，high右边比基准值大)
基准值7
x x x x 6 5 x x l h     此时基准值正在与l所代表元素比较h向左移动中（说明l位置是无用数据）
x x x x 5 5 x xl h     h数据复制给l,轮到下标l向左移动(h现在是无用数据)
x x x x 5 5 x x↑     两下标重合相等，此时应该放入基准值temp(h现在是无用数据)(low左边比基准值小，high右边比基准值大)
*********************************************************
*/int part(int arr[],int low,int high)
{//检查输入范围是否合法if(low>high){return -1;}//选定一个基准值(以左端作为基准值)int temp=arr[low];//注意:下标low所在数据被temp保存//结束循环的条件while(low<high){//比较右端,比基准大的仍然放在右边，不用管，继续向前判断下一个:故high--;while(temp<arr[high]&&low<high){high--;//下标向前移动，判断下一个}//条件不满足时出循环，将这个小数据放到左边，下标为low的地方(low数据已经被保存)arr[low]=arr[high];//开始比较左端:比基准小得仍然放左边，继续向后判断下一个while(temp>arr[low]&&low<high){low++;}//条件不满足，跳出循环，将这个小数据放到左边arr[high]=arr[low];//此时high所在数据，之前已经被放到循环前的low里了/*注意:这里内层循环增设了条件为low<high,图形解释:   见最下方《基准值临界情形图》PRO文字解释:当low与high相差为1时，假定low与low将值给high，开始判断high,此时high的值必定会满足，所以high会左移high移动到low的位置，仍然会满足值的条件条件high继续移动到low的左边，此时high值不满足条件；出循环并且交换数据；回到大循环，判断low<high*/}//运行到此，说明low==high;arr[high]=temp;return high;//基准所在下标low或者high都可以
}void quick_sort(int arr[],int low,int high)
{if(low>=high){return;}int mid=part(arr,low,high);quick_sort(arr,low,mid-1);quick_sort(arr,mid+1,high);
}int main()
{int arr[]={82,15,49,85,28,43,39,17,47,48};int len=sizeof(arr)/sizeof(arr[0]);printf("len=%d\n",len);//快速排序quick_sort(arr,0,9);//数据显示showData(arr,len);
}/*
*********************************************************
《基准值临界情形图》PRO     临界情形分析
基准值5
x x x x 6 3 x x xl h     此时基准值正在与l所代表元素比较l向右移中（说明h位置是无用数据）
x x x x 6 6 x x xl h     l数据复制给h,轮到下标h向左移动
x x x x 6 6 x x x↑       两下标重合相等，此时应该放入基准值temp(h现在是无用数据)
x x x x 6 6 x x xh l       内层循环不加low<high;则h会一直移动！直到小于基准值，才回到外层循环判断low<high
基准值7
x x x x 6 5 x x l h     此时基准值正在与l所代表元素比较h向左移动中（说明l位置是无用数据）
x x x x 5 5 x xl h     h数据复制给l,轮到下标l向左移动(h现在是无用数据)
x x x x 5 5 x x↑     两下标重合相等，此时应该放入基准值temp(h现在是无用数据)
x x x x 5 5 x xh l   内层循环不加low<high;则l会一直移动！直到大于基准值，才回到外层循环判断low<high
*********************************************************
*/

直接插入排序

//直接插入排序
void insert_sort(int arr[],int len)
{for(int i=1;i<len;i++)//{int temp=arr[i];//选定第i个，进行插入int j;for(j=i-1;j>=0&&arr[j]>temp;j--)//将在"我"之前的数据，依次向后搬运，直到遇到第一个比自己小的元素{arr[j+1]=arr[j];}arr[j+1]=temp;//插入位置！注意执行了"j--"才出的循环}
}

改良版冒泡排序

//改良版冒泡排序
void bubble_sort(int buf[],int len)
{int temp;int flag=1;for(int i=0;i<len&&flag;i++)//轮数{flag=0;//使用标志位前，标志位初始值for(int j=0;j<len-1-i;j++)//每轮比较次数{if(buf[j]>buf[j+1]){flag=1;//发生交换，标志位置1temp=buf[j+1];buf[j+1]=buf[j];buf[j]=temp;}}//一轮下来没有发生交换，排序已完成，跳出循环}
}