前言：
2016年5月21號(hào)開始學(xué)習(xí)排序算法及其主要思想炒瘟，并通過代碼實(shí)現(xiàn)
插入排序
插入排序有兩種：
- 直接插入排序
- 折半插入排序
直接插入排序
算法思想：
設(shè)有n + 1個(gè)記錄，存放在數(shù)組R中抛杨，重新安排記錄在數(shù)組中的存放順序，使得按關(guān)鍵字有序即R[0].key <= R2.Key <= ...<=R[n].key(有序表)
- 假設(shè)待排序的記錄存放在數(shù)組R[1..n]中朱监。
- 初始時(shí)臭埋，R[1]自成1個(gè)有序區(qū)，無序區(qū)為R[2..n]伞矩。
- 從i=2起直至i=n為止，依次將R[i]插入當(dāng)前的有序區(qū)R[1..i-1]中夏志，生成含n個(gè)記錄的有序區(qū)乃坤。
算法描述
- （1）若比較r[0] < r[i]時(shí)， j = i - 1; // 從第i個(gè)記錄向前測(cè)試插入位置沟蔑，用r[0]為輔助單元
- （2）若r[0].key >=r[j].key 轉(zhuǎn)(4)
- （3）若r[0].key < r[j].key時(shí)湿诊，r[j + 1] = r[j]; j--；轉(zhuǎn)(2) // 調(diào)整待插入位置
- (4) r[j + 1] = r[0];結(jié)束
算法實(shí)現(xiàn)
#include <stdio.h>
#define N 10
void insertSort(int a[],int length) {
int j;
for (int i = 1; i <= length; i++) {
a[0] = a[i]; // 將第i個(gè)待排序記錄賦值給a[0],a[0]位置為哨兵
j = i - 1; // 此時(shí)的j為哨兵的前一個(gè)元素
while (a[0] < a[j] && j >=0) { // 將第i個(gè)待排序記錄同前面的i - 1 個(gè)記錄比較瘦材，并為第j個(gè)記錄尋找合適的插入位置
a[j + 1] = a[j];
j--;
}
a[j + 1] = a[0]; // 此時(shí)的j為合適插入位置
}
}
void main() {
int a[N + 1],i;
for (i = 1;i <= N; i++) {
scanf("%d",&a[i]);
}
insertSort(&a,N);
printf("Input Sort:\n");
for (i = 1; i < N + 1; i++) {
printf("%d",a[i]);
}
}
算法分析
時(shí)間復(fù)雜度 O(n2)
- 向有序表(R1[0].key <= R[1].key <= ... R[j - 1].key)中逐個(gè)插入記錄的操作厅须，進(jìn)行了n - 1趟，每趟操作分為比較關(guān)鍵字和移動(dòng)記錄食棕，而比較的次數(shù)和移動(dòng)的次數(shù)取決于待排序列按關(guān)鍵字的初始排列朗和。
- 最好情況：待排序列已按關(guān)鍵字正序，比較次數(shù)Cmin = n - 1 次簿晓，移動(dòng)次數(shù)Mmin = 0 次
-
最壞情況：待排序列已按關(guān)鍵字逆序
最壞情況比較和移動(dòng)次數(shù).png -
平均情況：待排序可能出現(xiàn)的各種排列的概率相同
平均情況比較和移動(dòng)次數(shù).png - 直接插入算法的穩(wěn)定性：是穩(wěn)定的排序方法眶拉。
空間復(fù)雜度
- 需要一個(gè)輔助控件(監(jiān)視哨)，輔助空間復(fù)雜度S(n)=O(1)憔儿，此算法是就地排序
折半插入排序
直接插入排序算法漸變忆植，且容易實(shí)現(xiàn)。當(dāng)排序的數(shù)量n很小時(shí)谒臼，這是一種很好的排序方法唱逢。但是，通常待排序序列中的記錄數(shù)量n很大屋休，則不宜采用直接插入排序。折半插入排序（binary insertion sort）是對(duì)插入排序算法的一種改進(jìn)备韧，由于排序算法過程中劫樟，就是不斷的依次將元素插入前面已排好序的序列中。由于前半部分為已排好序的數(shù)列，這樣我們不用按順序依次尋找插入點(diǎn)叠艳，可以采用折半查找的方法來加快尋找插入點(diǎn)的速度奶陈。
算法思想：
折半插入排序
- 向有序表中插入一個(gè)記錄，插入位置是通過對(duì)有序表中記錄按關(guān)鍵字逐個(gè)比較得到的
- 平均情況下總比較次數(shù)n2/4
- 通過二分有序表來確定插入位置附较，既一次比較吃粒，通過待插入記錄與有序表居中的記錄按關(guān)鍵字比較，將有序列一份為二拒课，下次比較在其中一個(gè)有序子表中進(jìn)行徐勃，將字表又一分為二。這樣繼續(xù)下去早像，直到要比較字表中只有一個(gè)記錄時(shí)僻肖，比較一次就確定了插入位置
算法流程圖
算法實(shí)現(xiàn)
算法分析
時(shí)間復(fù)雜度 O(n2)
折半插入排序算法是一種穩(wěn)定的排序算法，比直接插入算法明顯減少了關(guān)鍵字之間比較的次數(shù)卢鹦，因此速度比直接插入排序算法快臀脏，但記錄移動(dòng)的次數(shù)沒有變，所以折半插入排序算法的時(shí)間復(fù)雜度仍然為O(n^2)冀自，與直接插入排序算法相同揉稚。附加空間O(1)。
- 穩(wěn)定性：是穩(wěn)定排序
空間復(fù)雜度
- 需要一個(gè)輔助控件熬粗，附加空間O(1)搀玖。，此算法是就地排序
希爾排序
希爾排序(Shell Sort)是插入排序的一種荐糜。也稱縮小增量排序巷怜，是直接插入排序算法的一種更高效的改進(jìn)版本。希爾排序是非穩(wěn)定排序算法暴氏。
算法思想：
希爾排序
- 選擇一個(gè)步長(zhǎng)序列t(1),t(2),...,t(<sub >k),其中t(i) > t(j), t(k) = 1延塑。
- 按步長(zhǎng)序列個(gè)數(shù)k，對(duì)序列進(jìn)行k趟排序
- 每趟排序根據(jù)對(duì)應(yīng)的步長(zhǎng)t(i),將待排序列分隔成若干長(zhǎng)度為m的子序列答渔，分別對(duì)各子表進(jìn)行直接插入排序聋涨。僅步長(zhǎng)因子為1時(shí)，整個(gè)序列作為一個(gè)表來處理裂问，表長(zhǎng)度即為整個(gè)序列的長(zhǎng)度喇聊。
算法流程圖
p:步長(zhǎng)因子 顏色相同：每趟排序根據(jù)對(duì)應(yīng)的步長(zhǎng)p,將待排序列分隔成若干長(zhǎng)度為m的子序列，分別對(duì)各子表進(jìn)行直接插入排序务豺。僅步長(zhǎng)因子為1時(shí)磨总，整個(gè)序列作為一個(gè)表來處理，表長(zhǎng)度即為整個(gè)序列的長(zhǎng)度笼沥。
算法實(shí)現(xiàn)
#include<stdio.h>
#include<math.h>
#define MAXNUM 10
void main()
{
void shellSort(int array[],int n,int t);//t為排序趟數(shù)
int array[MAXNUM],i;
for(i=0;i<MAXNUM;i++)
scanf("%d",&array[i]);
shellSort(array,MAXNUM,int(log(MAXNUM+1)/log(2)));//排序趟數(shù)應(yīng)為log2(n+1)的整數(shù)部分
for(i=0;i<MAXNUM;i++)
printf("%d ",array[i]);
printf("\n");
}
//根據(jù)當(dāng)前增量進(jìn)行插入排序
void shellInsert(int array[],int n,int dk)
{
int i,j,temp;
for(i=dk;i<n;i++)//分別向每組的有序區(qū)域插入
{
temp=array[i];
for(j=i-dk;(j>=i%dk)&&array[j]>temp;j-=dk)//比較與記錄后移同時(shí)進(jìn)行
array[j+dk]=array[j];
if(j!=i-dk)
array[j+dk]=temp;//插入
}
}
//計(jì)算Hibbard增量
int dkHibbard(int t,int k)
{
return int(pow(2,t-k+1)-1);
}
//希爾排序
void shellSort(int array[],int n,int t)
{
void shellInsert(int array[],int n,int dk);
int i;
for(i=1;i<=t;i++)
shellInsert(array,n,dkHibbard(t,i));
}
或：
#include <stdio.h>
#define MAXNUM 10
void shellSort(int a[],int n) {
int i,j,gap,x;
gap = n / 2; // 初始步長(zhǎng)一般為待排序文件長(zhǎng)度的一半
while (gap > 0) { // 當(dāng)步長(zhǎng)大于0時(shí)繼續(xù)排序
for ( i = gap; i < n; i++) {
// 從每個(gè)子序列的第一個(gè)位置開始比較
j = i - gap; //
while (j >= 0)
if (a[j] > a[j + gap]) { // (1) a[j]前面的元素蚪燕，(2) a[j + gap]后面的元素娶牌，如果(1) > (2) 交換兩個(gè)元素的位置
x = a[j];
a[j] = a[j + gap];
a[j + gap] = x;
j = j - gap; // 無符號(hào)，當(dāng)前子序列的下一個(gè)結(jié)點(diǎn)
printf("j--!%d",j);
} else j = -1;
}
gap = gap / 2; // 步長(zhǎng)減半
}
}
void main() {
int a[MAXNUM] = {26,76,83,56,13,29,50,78,30,11};
shellSort(a,MAXNUM);
for (int i = 0; i < MAXNUM; i++) {
printf("%d ",a[i]);
}
}
算法分析
時(shí)間復(fù)雜度 O(n2)
希爾排序是按照不同步長(zhǎng)對(duì)元素進(jìn)行馆纳，當(dāng)剛開始元素很無序的時(shí)候诗良，步長(zhǎng)最大，所以插入排序的元素個(gè)數(shù)很少鲁驶，速度很快鉴裹；當(dāng)元素基本有序了，步長(zhǎng)很小钥弯，插入排序?qū)τ谟行虻男蛄行屎芨呔独蟆Ｋ裕柵判虻臅r(shí)間復(fù)雜度]會(huì)比o(n^2)好一些寿羞。
- 穩(wěn)定性：是穩(wěn)定排序
空間復(fù)雜度
- 需要一個(gè)輔助控件猖凛，附加空間O(1)。绪穆，此算法是就地排序
冒泡排序
冒泡排序：
- 冒泡排序
- 優(yōu)化冒泡排序
算法思想：
- j = length - 1(j為數(shù)組最后一個(gè)元素)
- 若i >= j 辨泳，一趟冒泡結(jié)束
- 若a[j] < a[j - 1] 交換
- i＋＋下一趟
算法流程圖
算法實(shí)現(xiàn)
#include <stdio.h>
#define MAXNUM 10
void bubbleSort(int a[],int length) {
for (int i = 0; i < length - 1; ++i)
// 趟數(shù)，最后一趟已排序
for (int j = length - 1;j > i;--j) {
// 如果前一個(gè)元素大于后一個(gè)元素則交換
if (a[j] < a[j - 1]) {
a[j] = a[j] ^ a[j - 1];
a[j - 1] = a[j] ^ a[j - 1];
a[j] = a[j] ^ a[j - 1];
}
}
}
void main() {
int a[MAXNUM] = {26,76,83,56,13,29,50,78,30,11};
bubbleSort(a,sizeof(a) / sizeof(int));
for (int i = 0; i < MAXNUM ; i++) {
printf("%d ",a[i]);
}
}
優(yōu)化冒泡排序代碼：
#include <stdio.h>
#define MAXNUM 10
void bubbleSort(int a[],int length) {
int recordSwapValue;
int swapValue = 0;
for (int i = 0; i < length - 1;i++) {
recordSwapValue = swapValue; //i... recordSwapValue的索引為有序
for (int j = length - 1; j > recordSwapValue; j--) { // R[i...recordSwapValue]或R[0...recordSwapValue]區(qū)間有序的,遍歷區(qū)間由R[i...length] 縮減到[recordSwapValue..length]玖院。
if (a[i] > a[i - 1]) {
a[j] = a[j] ^ a[j - 1];
a[j - 1] = a[j] ^ a[j - 1];
a[j] = a[j] ^ a[j - 1];
swapValue = j; // 記錄交換位置的索引值
}
}
// 如果值相當(dāng)菠红，整個(gè)過程
if (recordSwapValue == swapValue) {
break;
}
}
}
void main() {
int a[MAXNUM] = {26,76,83,56,13,29,50,78,30,11};
bubbleSort(a,sizeof(a) / sizeof(int));
for (int i = 0; i < MAXNUM ; i++) {
printf("%d ",a[i]);
}
}
算法分析
時(shí)間復(fù)雜度 O(n2)
- 向有序表(R1[0].key <= R[1].key <= ... R[j - 1].key)中逐個(gè)插入記錄的操作，進(jìn)行了n - 1趟难菌，每趟操作分為比較關(guān)鍵字和移動(dòng)記錄试溯，而比較的次數(shù)和移動(dòng)的次數(shù)取決于待排序列按關(guān)鍵字的初始排列。
- 最好情況：待排序列已按關(guān)鍵字正序郊酒，比較次數(shù)Cmin = n - 1 次遇绞，移動(dòng)次數(shù)Mmin = 0 次
-
最壞情況：待排序列已按關(guān)鍵字逆序
最壞情況比較和移動(dòng)次數(shù).png -
平均情況：待排序可能出現(xiàn)的各種排列的概率相同
平均情況比較和移動(dòng)次數(shù)
* 冒泡排序的穩(wěn)定性：是穩(wěn)定的排序方法。
空間復(fù)雜度 Ｏ（１）
- 需要一個(gè)輔助控件(監(jiān)視哨)燎窘，輔助空間復(fù)雜度S(n)=O(1)摹闽，此算法是就地排序
快速排序
算法思想：
快速排序
* 快速排序是通過關(guān)鍵字、交換記錄褐健，以某個(gè)記錄為界（該記錄稱謂支點(diǎn)）付鹿，將待排序列分成兩部分。其中一部分所有記錄的關(guān)鍵字大于支點(diǎn)記錄的關(guān)鍵字蚜迅，另一部分所有記錄的關(guān)鍵字小于支點(diǎn)記錄的關(guān)鍵字舵匾。將待排序列按關(guān)鍵字以支點(diǎn)記錄分成兩部分的過程，稱為一次劃分谁不。對(duì)各部分不斷劃分坐梯，直到整個(gè)序列按關(guān)鍵字有序，整個(gè)排序過程可以遞歸刹帕。
算法描述
設(shè) 1 <= p < q <= n 烛缔，r[p], r[p + 1]馏段，...，r[q]為待排序列
- (1) low = p;high = q;
r[0] = r[low]; // 取第一個(gè)記錄為支點(diǎn)記錄践瓷，low位置暫設(shè)為支點(diǎn)空位 - (2) 若low = high, 支點(diǎn)空位確定，即為low
r[low] = r[0];
否則, low < high搜索需要交換的記錄亡蓉，并交換之晕翠。 - (３)若low < high 且r[high].key >= r[0].key // 從high所指向位置向前搜索，至多到low + 1 位置
high = high - 1砍濒； 轉(zhuǎn)3 // 尋找r[high].key < r[0].key
r[low] = r[high]; // 找到r[high].key
