各种排序算法-上

//#include <bits/stdc++.h> //编译速度慢

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

//思考题： 给定一个序列，求如果用冒泡排序，需要交换多少次

void bubble_sort(vector<int> &q)
{
    for(int i = q.size()-1; i > 0; i--){// 从小到大排，后面是有序的，就可以不用考虑了，所以倒着写方便；外层循环控制边界
         bool flag = false; // 加优化， 记录有无进行交换操作
         for(int j = 0; j+1 <= i; j++)// 用最靠近末端（边界）的下标去接近边界
            if(q[j] > q[j+1]){
                swap(q[j],q[j+1]);
                flag = true ;
            }
         if(!flag) break; //这个优化很重要
    }

}

void select_sort(vector<int> &q)
{
    for(int i = 0; i < q.size(); i++){
        int minIndex=i;
        for(int j = i + 1; j < q.size(); j ++)
        if(q[j-1] > q[j]){
            minIndex = j;
        }
        int tmp = q[i];
        q[i] = q[minIndex];
        q[minIndex] = tmp;

    }
}

void insert_sort(vector<int> &q){
    for(int i = 1; i < q.size(); i++ ){ //第一个元素相当于排好序了，从1开始
        int t = q[i], j;
        for(j = i - 1; j >= 0; j--){
            if(q[j] > t){
                q[j+1] =q[j];
            }
            else break;
        }
        q[j+1] = t;
    }
}

int main()
{
   int n;
   vector<int> q;

   cin >> n;
   for(int i=0,t; i < n; i++ ) {
    cin >> t;
    q.push_back(t);
   }

   //bubble_sort(q);
   //select_sort(q);、
   insert_sort(q);

   for(auto x : q) cout << x << ‘ ‘;
   cout << endl;

   return 0;
}