四种排序算法

前言:经过昨天做的排序算法题,发现自己这么简单的题都忘记怎么做了,感觉很难受,今天复习整理了一遍,写成一个文章,以便日后复习,其中冒泡、选择、插入三种算法的思路和图片来自于B站up主"正月点灯笼",感谢你的讲解,我觉得你讲的非常好!

冒泡排序

例如 3、7、4、2、6、1这一个数组,我们对它进行升序的一个排序

1、首先从左往右两两进行比较,若左>右,则交换位置,进行第一趟排序

img

对于这第一趟的排序,并不能保证从左往右一定都是正确的升序排序,但是一定能保证最大的数已经排在了最右边

img

由此,我们可以得到一个思路,在第一趟排序后,我们只需要对这个长度为6的数组左边5个数字再进行一次冒泡排序,然后再对左边4个数字再进行一次冒泡排序,以此类推.....

img

#include <stdio.h>
/*
冒泡排序算法
*/


 /***
 * @Description:交换函数,交换括号内的参数 
 * [@Param](https://my.oschina.net/u/2303379): &a,&b
 * [@return](https://my.oschina.net/u/556800): 
 * [@Author](https://my.oschina.net/arthor): JaneRoad
 * [@Date](https://my.oschina.net/u/2504391): 2020/4/1
 */
void swap(int &a, int &b)
{
    int temp;
    temp = a;
    a = b;
    b = temp;
}



/***
* @Description:一次冒泡函数,将数组中最大的数移到最右边
* @Param: arr[],n(数组,数组长度)
* @return: 
* @Author: JaneRoad
* @Date: 2020/4/1
*/
void bubble(int arr[],int n){
    int i;
    for(i=0;i<n-1;i++){
        if(arr[i]>arr[i+1]){
            swap(arr[i],arr[i+1]);
        }
    }
}



/***
* @Description:冒泡排序函数,实现升序排序 
* @Param: arr[],n(数组,数组长度)
* @return: 
* @Author: JaneRoad
* @Date: 2020/4/1
*/
void bubbleSort(int arr[],int n){
    int i;
    for(i=n;i>=1;i--){
        bubble(arr,i);
    }
}



int main()
{
    int arr[] = {12,13,15,20,0,-1,-10,100,9};
    bubbleSort(arr,9);
    for(int i=0;i<9;i++){
        printf("%d\n",arr[i]);
    }
    return 0;
}

最终结果:

img

选择排序

例如 3、7、4、2、6、1这一个数组,我们对它进行升序的一个排序

首先找出[3、7、4、2、6、1]中最大的数字,将其与数组末位数字进行交换,然后再对前五个数字,即

[3、1、4、2、6] 中找出最大数字,再与末位数字进行交换,这样以此类推,就可以将这个数组进行升序排列

img

#include <stdio.h>
/*
选择排序算法学习
*/


/***
* @Description:交换函数,交换括号内的参数
* @Param: &a,&b
* @return:
* @Author: JaneRoad
* @Date: 2020/4/1
*/
void swap(int &a, int &b)
{
    int temp;
    temp = a;
    a = b;
    b = temp;
}


/**
* @Description: 遍历寻找当前数组中最大的数的数组位置
* @Param: arr[],n(数组,数组长度)
* @return: pos
* @Author: JaneRoad
* @Date: 2020/4/1
*/
int findMaxPos(int arr[],int n){
    int max=arr[0];
    int pos=0;
    for (int i = 0; i <n ; i++) {
        if(arr[i]>max){
            max=arr[i];
            pos=i;
        }
    }
    return pos;
}



/**
* @Description: 选择排序函数
* @Param: arr[],n(数组,数组长度)
* @return: 
* @Author: JaneRoad
* @Date: 2020/4/1
*/
void selectionSort(int arr[],int n){
    while(n>1){
        int pos=findMaxPos(arr,n);
        swap(arr[pos],arr[n-1]);
        n--;
    }
}


int main()
{
    int arr[] = {12,13,15,20,0,-1,-10,100,9};
    selectionSort(arr,9);
    for(int i=0;i<9;i++){
        printf("%d\n",arr[i]);
    }
    return 0;
}

插入排序

例如 3、7、4、2、6、1这一个数组,我们对它进行升序的一个排序

插入排序的思想就是,把一段数字分成两段,一段时间排好顺序的,一段时间未排好的。

例如:

img

图中[3、6、7] 就是一段排好顺序的,[4、2、1、5]就是未排好的,我们要想办法把4、2、1、5依次插到前面一段已经排好顺序的段落中正确的位置,这样就是插入排序。

我们知道了原理如何转化为代码思路呢?

我们以3、6、7、4为例

1、数组中的3、6、7已经是正确顺序,我们要想办法把4插入到它应该去的地方,我们设置一个值为key,key=4

然后我们再设置一个i,指向4所在的数组位置,即i=3 ,4和它的前一位数字7进行比较,7比4大所以我们使arr[3]=arr[2],也就是把4覆盖成7

img

2、完成上一步后,我们让i--,也就是i指向前一位数组位置,再次比较6和4(key),6比4大,所以再次arr[2]=arr[1],也就是把原本的7覆盖成6,

img

3、完成上一步后,i--,i来到了arr[1],3与4进行比较发现3比4小,那么条件不成立,4应该在此时i指向的数组位置,即arr[1]=key

img

img

但是这个方法要注意一点

img

如上图,2是最小的数字,他应该在最左边,但是在程序中,当它移动到arr[0]的位置时,他并不知道自己在数组最左端,它再找前一位数字进行比较时,就会报错,所以当i=0时,必须要停止。

在实际代码中,我们通常把第一个数字当成一个整体,它本身就是一个已经排好序的一段数字,尽管它只是单个数字,然后从后往前插入排序

img

#include <stdio.h>
/*
插入排序算法学习
*/

/***
* @Description:插入函数,数组中从后往前不断插入数字到正确位置
* @Param: arr[],n
* @return:
* @Author: JaneRoad
* @Date: 2020/4/1
*/
void insert(int arr[],int n){
    int key=arr[n];
    int i=n;
    while(arr[i-1]>key){
        arr[i]=arr[i-1];
        i--;
        if(i==0){
            break;
        }
    }
    arr[i]=key;
}

/***
* @Description:插入排序函数,调用插入函数
* @Param: arr[],n
* @return:
* @Author: JaneRoad
* @Date: 2020/4/1
*/
void insertionSort(int arr[],int n){
    int i;
    for (int i = 0; i < n; i++) {
        insert(arr,i);
    }
}


int main()
{
    int arr[] = {12,13,15,20,0,-1,-10,100,9};
    insertionSort(arr,9);
    for(int i=0;i<9;i++){
        printf("%d\n",arr[i]);
    }
    return 0;
}

快速排序

快速排序是我今天早上一早上慢慢想,跟着断点读示范代码领悟的,没有查资料,所以记得很清晰。

例如 3、6、7、4、2、1、5这一个数组,我们对它进行升序的一个排序

1、选取基准数3,设置头指针、尾指针,分别指向数组第一个元素和最后一个元素

2、基准数3与尾指针指向数字5比较,3<5且3在5左边,正确,不交换,尾指针前移一位,指向1

3、基准数3与尾指针指向数字1比较,3>5但3在1左边,做交换,arr[0]=1,arr[5]=3,由于此时尾指针指向了基准数3,故前指针后移一位,指向6。

4、基准数3与头指针指向数字6比较,3<6但3在6右边,做交换,尾指针前移一位,指向2

5、基准数3与尾指针指向数字2比较,3>2但3在2左边,做交换,头指针后移一位,指向7

6、基准数3与头指针指向数字7比较,3<7但3在7右边,做交换,尾指针前移一位,指向4

7、基准数3与尾指针指向数字4比较,3<4且3在4左边,正确,不做交换,尾指针前移,发现尾指针与头指针位置重合,第一趟快速排序完成

img

此时的数组是 [1、2、3、4、7、6、5]

我们可以发现最中间的4,左边都是比它小的数右边都是比它大的数

img

此时4左边的数字为一组,右边的数字为一组,分别递归调用快速排序,以此类推,即可完成数组排序

#include <stdio.h>
/*
快速排序算法学习
*/
/***
* @Description:交换函数,交换括号内的参数
* @Param: &a,&b
* @return:
* @Author: JaneRoad
* @Date: 2020/4/1
*/
void swap(int &a, int &b)
{
    int temp;
    temp = a;
    a = b;
    b = temp;
}
/***
* @Description:快速排序算法
* @Param: arr[],start,end(数组,数组头元素位置,数组尾元素位置)
* @return:
* @Author: JaneRoad
* @Date: 2020/4/1
*/
void quickSort(int arr[] ,int start, int end)
{
    int arrBase, arrMiddle;
    //arrBase为基准值,arrMiddle为一趟快速排序下来后,最中间的数字在数组中的位置(是第几个元素)
    int tempStart = start,tempEnd = end;

    //当头指针和尾指针重合时,跳出函数
    if(tempStart >= tempEnd)
        return;

    //拷贝一个基准值作为后面比较的参数
    arrBase = arr[start];
    while(start < end)
    {
        while(start < end && arr[end] > arrBase)
            end--;
        if(start < end)
        {
            swap(arr[start], arr[end]);
            start++;
        }

        while(start < end && arr[start] < arrBase)
            start++;
        if(start < end)
        {
            swap(arr[start], arr[end]);
            end--;
        }
    }
    arr[start] = arrBase;
    arrMiddle = start;

    //左右分别进行递归
    quickSort(arr,tempStart,arrMiddle-1);
    quickSort(arr,arrMiddle+1,tempEnd);
}


int main()
{
    int myArr[] = {12,13,15,20,0,-1,-10,100,9};
    int arrLength = sizeof(myArr)/sizeof(int);//数组长度
    quickSort(myArr,0,arrLength-1);
    for(int i=0;i<arrLength;i++){
        printf("%d\n",myArr[i]);
    }
    return 0;
}
# 排序 

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×