13518219792
插入排序：
算法簡介：接插入排序(Insertion Sort)的基本思想是：每次將一個待排序的記錄，按其關鍵字大小插入到前面已經排好序的子序列中的適當位置，直到全部記錄插入完成為止。時間復雜度為O(n^2)。 最穩定的排序算法但是效率很低
代碼實現：
void InsertSort(int *arr,int n)
{
for (int index = 0; index < n-1; ++index)
{
int end = index+1;
int tmp = arr [end];
while (end>0&&tmp1)//由于gap=gap/3+1 最小值為1 則在gap=1時跳出循環
{
gap = gap / 3 + 1; //{ 2, 8, 9, 6, 1, 3, 4, 5, 7, 0 ,-1,-2}//注意這里的＋1 當gap=1時此時排序等同于插入排序 但是由于之前將最小的數據已經移到最左邊所以效率
//高于插入排序
for (int index = 0; index = 0 && arr [end]>tmp) {
arr[end+gap] = arr [end];
end -=gap;//此時插入間距為end
}
arr[end+gap] = tmp;
}
}
}
附注：上面希爾排序的步長選擇都是從n/3+1開始，每次再取上一次的三分之一加1，直到最后為1。關于希爾排序步長參見維基百科：http://zh.wikipedia.org/wiki/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F
冒泡排序：20世紀經典算法之一，
原理是臨近的數字兩兩進行比較,按照從小到大或者從大到小的順序進行交換,這樣一趟過去后,大或最小的數字被交換到了最后一位,再進行第二趟冒泡，由此我們可以寫出以下代碼：
void BubbleSort(int *arr, int n)
{
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n - i - 1; ++j)
{
if (arr [j]>arr[j + 1])
swap( arr[j], arr [j + 1]);
}
}
}
這里我們設立一個標記變量 flag用來標記數列中的數是否在循環結束前就已經排好序
代碼改進如下：
void BubbleSort(int *arr, int n)
{
bool flag = true ;
int k = n ;
while (flag)
{
flag = false;
for (int i = 1; i < k; ++i)
{
if (arr [i - 1] 0)
{
int k = flag;
flag = 0;
for (int j = 1; j < k; ++j)
{
if (arr [j - 1] > arr[j])
{
swap( arr[j - 1], arr [j]);
flag = j;//后面的已經排序好 記錄下下一次排序的終點
}
}
}
}
雖然有了這么多優化，但是冒泡排序總體還是一種效率很低的排序，數據規模過大時不適合使用這種排序
堆排序：
堆的定義：
1.堆是一顆完全二叉樹
2.父結點總是大于或等于（小于或等于）任何一個子節點
3每個結點的左子樹和右子樹都是一個二叉堆
當父結點總是大于或等于任何一個子節點值時為大堆。反之則為最小堆
堆的結構示意圖如下：
存儲方式：
我們使用數組來存儲一個堆，可以看出設父節點下標值為i 其左孩子下標值為2*i+1,右孩子為2*1+2；
代碼實現如下：
void AdJust_down(int *arr, int parent, int size )
{
int child = 2 * parent +1;
while (child arr[child])
{
++child;
}
if (arr [parent]> arr[child])
break;
swap( arr[parent ], arr[child]);
parent = child;
child = 2 * parent;
}
}
void HeapSort(int *arr,int n)
{
for (int i = n/2-1; i >= 0; --i)
{
AdJust_down( arr, i, n );
}
for (int i = n - 1; i >= 1; --i)
{
swap( arr[0], arr [i]);
AdJust_down( arr, 0, i);
}
}
思路分析：
1.如果要對數字進行升序，我們首先首先將數組初始化為原始大堆
for (int i = n/2-1; i >= 0; --i)
{
AdJust_down( arr, i, n );//從最后一個非葉子節點開始調整
}
2.進行排序（以升序為例）
大堆的性質為：大的數據一定在堆頂將堆頂和堆最后一個元素進行交換，則大的數字此時在數字尾部，再將堆頂元素下調，且堆的大小減1，知道堆大小為1循環結束，排序完成。
代碼如下：
for (int i = n - 1; i >= 1; --i)
{
swap( arr[0], arr [i]);
AdJust_down( arr, 0, i);
}
選擇排序
選擇排序（Selection sort）是一種簡單直觀的排序算法。它的工作原理是每一次從待排序的數據元素中選出最小（或大）的一個元素，存放在序列的起始位置，直到全部待排序的數據元素排完。 選擇排序是不穩定的排序方法
為了減少比較的次數，我們一次遍歷同時選出大值和最小值，代碼實現如下：
void SelectSort(int *arr, int n)
{
int i = 0, j = n - 1;
int max = j;
int min = i;
int left = 0; int right = n - 1;
while (left<=right)
{
min = left;
max = right; ///！！?。。。。。。。。≈攸c
for (i = left, j = right; i <= j; i++)
{
if (arr [min]>arr[i])
min = i;
if (arr [max] < arr[i]) ////{ 2, 9, 6, 1, 3, 4, 5, 7, 0 ,-8,1,-2}
max = i;
}
if (left != min)
{
swap( arr[left], arr [min]);
if (max == left)
max = min;
}
if (right != max)
swap( arr[right], arr [max]);
left++;
right--;
}
}
這里我們必須注意到，以升序為例，如果一次遍歷找到的大值剛好在數組左邊，此時肯定會先被移走，此時就大值得下標就得更新為轉移后的位置
快速排序：
該方法的基本思想是：
1．先從數列中取出一個數作為key。
2．分區過程，將比這個數大的數全放到它的右邊，小于或等于它的數全放到它的左邊。
3．再對左右區間重復第二步，直到各區間只有一個數。
代碼實現如下：
int PartSort(int *arr, int left, int right)
{
int key = arr [right]; //{ 10,2, 8, 9, 6, 1, 3, 4, 5, 7, 0 ,-1,-2,-100};
int begin = left ;
int end = right - 1;
while (begin=key)
{
end--;
}
if (begin < end)
swap( arr[begin], arr [end]);
}
if (arr [begin]>arr[right])
{
swap( arr[begin], arr [right]);
return begin;
}
return right ;
}
void QuickSort(int *arr, int left,int right)
{
if (left >= right)
return;
int div = PartSort(arr , left, right);
QuickSort( arr, div + 1, right );
QuickSort( arr, left , div - 1);
} 創新互聯www.cdcxhl.cn，專業提供香港、美國云服務器，動態BGP最優骨干路由自動選擇，持續穩定高效的網絡助力業務部署。公司持有工信部辦法的idc、isp許可證， 機房獨有T級流量清洗系統配攻擊溯源，準確進行流量調度，確保服務器高可用性。佳節活動現已開啟，新人活動云服務器買多久送多久。
