?????? 排序，對于大家再熟悉不過了吧。我們之前在學習c語言的時候接觸過的冒泡排序，選擇排序等。今天給大家介紹兩種新的排序。

1、直接插入排序

升序排列：將第一個數確定好，從下標為1的數開始插入，如果插入的數比前一個數大，就插入到前一個數后的位置。否則，將前一個數的位置后移，再與再往前的數比較，依次類推。

時間復雜度為：O(N*N)???????? 最好情況：O(N)

主要實現代碼（vs2013）:

	#pragma once#include<iostream>using namespace std;void InsertSort(int *a,size_t size){for(size_t i = 1; i < size; ++i){int end = i-1;int tmp = a[i];while(end >= 0){if(tmp < a[end]) //升序  //if(tmp > a[end]) //降序{a[end+1] = a[end];--end;}else{break;}}a[end+1] = tmp;}}void Display(int *a,size_t size){for(size_t i = 0; i < size; ++i){cout<<a[i]<<" ";}cout<<endl;}void TestInsert(){int a[] = {2,5,4,9,3,6,8,7,1,0};size_t size = sizeof(a)/sizeof(a[0]);InsertSort(a,size);Display(a,size);}

運行結果：

2、希爾排序

?????? 當在插入排序中，數據特別多時，且不是有序的。這時采用插入排序就特別的慢。尤其是對于升序情況，所給的數據是降序，那么就需要每次挪動數據。這就顯得效率比較低了。于是引入了希爾排序，將它們先排列的接近有序，再進行插入排序就容易多了。

主要實現代碼（vs2013）：

void ShellSort(int* a,size_t size)
{int gap = size;int end = 0;int tmp = 0;while(gap > 1){gap = gap/3+1;for(size_t i = gap; i < size; ++i){end = i-gap;tmp = a[i];while(end >= 0){if(tmp > a[end])  //降序   //if(tmp < a[end]) 升序{a[end+gap] = a[end];end -= gap;}elsebreak;}a[end+gap] = tmp;}}
}void Display(int *a,size_t size)
{for(size_t i = 0; i < size; ++i){cout<<a[i]<<" ";}cout<<endl;
}void TestInsert()
{int a[] = {0,1,2,3,4,5,6,7,8,9};size_t size = sizeof(a)/sizeof(a[0]);ShellSort(a,size);Display(a,size);
}

運行結果：