数据结构与算法——排序算法

参考链接
十大经典排序算法

排序分为内部排序和外部排序

在这里插入图片描述

冒泡排序
（1）原理描述
重复地走访要排序的数列、一次比较两个元素，如果他们的顺序错误就把他们交换过来。
序列终止条件，重复地进行直到没有再需要较好为止。
冒泡：越来越小的元素会慢慢“浮”到水面
（2）相关代码
步骤：
a.用一个while外层循环和一个for内层循环对数组进行遍历
b.按照顺序遍历数组判断相邻元素的元素大小
c.记录是否发生交换，循环终止条件是遍历整个数组不再发生交换

#include 
using namespace std;
template //整数或浮点数皆可使用,若要使用类(class)或结构体(struct)时必须重载大于(>)运算符
void bubble_sort(T arr[], int len) {
    while (true)    //用while建立双循环
    {
        flag = 0;   //用来判断数据是否发生交换的标志
        for(int i = 0;i arr[i+1]){
                swap(arr[i],arr[i+1]);
                flag = 1;
            }   
        }
        if (flag == 0){
            break;
        }
    }
    
        
}
int main() {
        int arr[] = { 61, 17, 29, 22 };  //数组定义时等号左侧是[]等号右侧是{}
        int len = (int) sizeof(arr) / sizeof(*arr); //数据的长度
        //cout<
        bubble_sort(arr, len);
        for (int i = 0; i < len; i++)
                cout << arr[i] << ' ';
        cout << endl;
        float arrf[] = { 17.5, 19.1, 0.6, 1.9, 10.5 };
        //cout<
        len = (float) sizeof(arrf) / sizeof(*arrf);
        bubble_sort(arrf, len);
        for (int i = 0; i < len; i++)
                cout << arrf[i] << ' '< 
2.选择排序 
选择排序
 （1）原理描述
 首先在未排序序列中找最大（小）元素，存放到排序序列的起始位置；
 再从剩余未排序元素中继续寻找最大（小）元素，然后放到已排序序列的末尾‘
 直到所有元素排序完毕，算法复杂度恒定
 （2）相关代码
 步骤
 
# include
# include

using namespace std;
void selected_sort(vector&nums){
    for(int i = 0; i < nums.size();i++){
        int min = i;
        for (int j = i+1; j < nums.size(); j++) //遍历元素找最小值的过程
        {
            if(nums[j]nums = {6,3,5,1,2};
    selected_sort(nums);
    for(int i = 0; i < nums.size();i++){
        cout< 
3.插入排序 
插入排序
 （1）原理描述
 插入动作发生在未排序部分
 构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应的位置插入。
 （2）相关代码
 步骤
 a.遍历数组是为了选择一个执行插入操作的元素，eg 6,3,5遍历第一次让3插入到6前面
 b.插入操作从后往前遍历，与冒泡排序非常相似
 
# include 
# include 
using namespace std;

void insert_sort(vector &nums){            //插入算法感觉与冒泡算法相似 ，参数传递是传递引用
        for(int i = 0; i-1;j--){
                        if(nums[j]>nums[j+1]){ //每一个元素与前面的元素比较大小,出过错的地方
                                swap(nums[j],nums[j+1]);
                        }
                }
        }
}

int main(){
    vectornums = {6,3,5,1,2};
    insert_sort(nums);
    for(int i = 0; i < nums.size();i++){
        cout< 
4.快排序
 快排序
 （1）原理描述
 从数列中挑选出一个元素为“基准”pivot，
 通过一趟排序把所有数据分割成独立的两部分，其中一部分数据比另一部分所有数据要小，
 在按这种方法对两部分数据进行快速排序。
 for()用于明确次数的循环，while用于条件判断不确定循环次数的循环
 （2）相关代码
 步骤
 a.确定比较基准
 b.用left和right两个指针来定位比pivot小和比pivot大的元素
 c.再次调用快排序
 出现的问题是，没有写return语句陷入了死循环。
 
# include
# include

using namespace std;
void quick_sort(vector&nums,int low,int high){
    if(low>=high){  //不写这一个语句会陷入死循环，所以不报错但是没有结果
        return;
    }
    int left = low;
    int right = high;
    int pivot = nums[(left+right) / 2];
    while(left<=right){
        while(nums[left]pivot){
            right--;
        }
        
        swap(nums[left],nums[right]); //不加对left和right的大小判断，容易跳过结点，然后陷入死循环
        left++;
        right--;          
        
    }
    quick_sort(nums,low,right);//没有重叠的部分，跳出while循环后是指left>right的时候
    quick_sort(nums,left,high);//把left和right的位置弄反陷入了死循环
}

int main(){
    vectornums = {6,3,5,1,2};
    quick_sort(nums,0,nums.size()-1);
    for(int i = 0; i < nums.size();++i){
        cout<