排序算法集锦

1冒泡排序

思想：相邻数据比较，数组中每两个相邻的数字都要比较，从头比较到末尾确定一个数所在的位置；

如此，N个数，比较NUM=n-1个轮次，每个轮次做n-num次两两比较；

代码如下：（这里为什么改变数组的内容，形参传的不是arr[]的指针，因为形参int arr[] = int *arr,形参虽然是一个副本，是一份拷贝，但是指针所指向的地址是一样的）

//排序算法1 冒泡排序
#include "stdafx.h"
#include"stdio.h"
#include"iostream"
void MPsort(int arr[],int n)
{
    //从小打大，规则：小的放左边，大的放右边。从左到右完成一次比较，最后的一个数就是定住的
    /*
    *arr[]= {1,3,2,5,4,6,8,0}
    第一轮比较 7次，确定最后一个数
    第二轮比较6次，确定倒数第二个数
    第三轮比较5次，确定倒数第三个数
    。。。。
    第N轮比较一次，确认第1,2位的数
    */

    /*数组中有N个数，比较i=n-1轮，每轮次比较 n-i次*/

    for (int i = 0; i < n-1; i++)
    {
        for (int j = 0; j < n - i - 1; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

int main()
{
    int arrs[] = {1,4,2,3,6,5,7,0,9,8};
    MPsort(arrs, 10);
    for (int i = 0; i < 10; i++)
    {
        std::cout << arrs[i] << " ";
    }
    return 0;
}

 2 快速排序

思想：选择基值位置，以及基值，数组中比这个值小的数据都放在这个值的左边，比这个值大的数据，都放在这个值的右边

再分别对这个基准值位置的左侧和右侧做同样的操作，直到只有一个数值（既没有左边也没有右边），停止；

//排序算法1 快速排序，递归
#include "stdafx.h"
#include"stdio.h"
#include"iostream"
/*
找一个基准值，第一趟，比基准值小的数字，都放在基准值的左边，比基准值大的，都放在基准值的右边
对左边的部分进行递归
对右边的部分进行递归
结束的标志：本次比较就只剩下一个数即下标left=right
*/


int OneStepSort(int* arr, int left, int right)
{
    int key_value = arr[left];//取数组的最左边的值为基，比基值小的放在左边，比基值大的放在右边

    while (left <right)
    {
        while (arr[right]> key_value&& left <right)//为什么外层循环已经有了left<right,这里还要写；防止覆盖基值所在位置的内存
        {
            right--;
        }
        arr[left] = arr[right];
        left++;
        while (arr[left] < key_value && left <right )
        {
            left++;
        }
        arr[right] = arr[left];
        right--;

        for (int i = 0; i < 7; i++)
        {
            std::cout << arr[i] << " ";
        }
        std::cout << "\n";
    }
    arr[left] = key_value;
    std::cout <<"----------"<< "\n";
    return left;
}
void Quicksort(int* arr, int left,int right)
{
    int posBaseKay = 0;//基准值的位置
    if (left < right)
    {
        posBaseKay = OneStepSort(arr, left, right);
        Quicksort(arr, left, posBaseKay - 1);
        Quicksort(arr, posBaseKay + 1, right);
    }

    return;

}



int main()
{
    int arrs[] = {9,4,2,3,6,5,7};
    Quicksort(arrs, 0, 6);
    for (int i = 0; i < 7; i++)
    {
        std::cout << arrs[i] << " ";
    }
    return 0;
}