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

目录

快速排序

直接插入排序

改良版冒泡排序

快速排序

理解：

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

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

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

    即将左端到基准数据作为范围，传入；这个范围又会产生新的范围：左端到基准数据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 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右边比基准值大)
*********************************************************
*/

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 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现在是无用数据)
x x x x 6 6 x x x
      h 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 x
        l h     h数据复制给l,轮到下标l向左移动(h现在是无用数据)
x x x x 5 5 x x
          ↑     两下标重合相等，此时应该放入基准值temp(h现在是无用数据)
x x x x 5 5 x x
          h 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;//发生交换，标志位置1
                temp=buf[j+1];
                buf[j+1]=buf[j];
                buf[j]=temp;
            }
        }
        //一轮下来没有发生交换，排序已完成，跳出循环
    }
}