插入排序法之——直接插入排序、折半插入排序、希爾排序

// test20.cpp : 定義控制臺應用程序的入口點。
//

#include "stdafx.h"
#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<stack>
#include<cstring>
#include<string.h>
#include<deque>
#include <forward_list>using namespace std;class Solution {
public:void InsertSort(vector<int> &vec)//直接插入排序{for (int i = 1;i < vec.size();++i)//從第二個數開始進行直接插入排序{int num = vec[i];int flag = -1;//如果flag==-1，則是沒有找到比num大的數，所以位置保持不變for (int j = 0;j < i;++j) {if (num < vec[j])//在前i個數中找到大于或等于num的數，插入到第一個大于num的數前面{flag = j;break;}}//      for (flag;flag <= i;++flag)if (flag == -1) continue;//用continue，而不是break，結束本次循環，執行下次循環while (i > flag){vec[i] = vec[i-1];i--;}vec[flag] = num;}print(vec);}void BInsertSort(vector<int> &vec){for (int i = 1;i < vec.size();++i){int num = vec[i];int flag = -1;//大于num的節點位置，即插入num的位置int low = 0;  //用折半查找發找到第一個大于num的節點位置int high = i;int mid = (low + high) / 2;while (low <= high){if (num >= vec[mid])//要找到第一個大于num的位置,注意這里的等于號！！！！！！！！！！！！！！！{low = mid + 1;mid = (low + high) / 2;}else {high = mid - 1;mid = (low + high) / 2;}}//如果high==i,就是沒找到大于num的數，不用移動//如果low==0,就是要把num插入最前面//如果不符合上述兩個條件，則把節點插入到low前面if(high==i)continue;else flag = low;//  if (flag == -1) continue;while (i>flag){vec[i] = vec[i - 1];--i;}vec[flag] = num;}print(vec);}void ShellInsertSort(vector<int> &vec){SheellSort(vec,1);}//希爾排序要設置排序間隔void  SheellSort(vector<int> &vec,int dk)//分成dk組，每一組進行直接插入排序{for (int i = dk;i < vec.size();++i)//從第二個數開始判斷{int num = vec[i];int flag = -1;int j = i - dk;for (j;j >=0;j -= dk)//從0號單元開始比較，依次往后比較，找到第一個小于num的數字，插入其后面{//如果沒有找到，則fla==-1，插入到最前面if (num >= vec[j])//如果flag==j，則不用做處理{flag = j;break;}}if (flag == -1){while (i>j+dk){vec[i] = vec[i-dk];i = i - dk;}vec[j + dk] = num;}else{while (i>flag + dk){vec[i] = vec[i - dk];i = i - dk;}vec[flag + dk] = num;}}print(vec);}void print(vector<int> &vec)//打印數據{for (auto it = vec.begin();it != vec.end();++it){cout << *it << "  ";}cout << endl;}};
int main()
{
//  vector<int> vec = { 1,3,2,7,6,5,4,8,9 };
//  vector<int> vec = { 1,3,2};vector<int> vec = { 49,38,65,97,76,13,27,49,55,4};//vector<int> vec = { 49,38,65,97,76,13,27,55,4 };Solution so;//原來的序列cout << "原來的序列:   ";so.print(vec);//直接插入排序：cout << "直接插入排序：";so.InsertSort(vec);//折半排序cout << "折半插入排序：";so.BInsertSort(vec);//希爾排序cout << "希爾排序：";so.ShellInsertSort(vec);return 0;
}