数据结构

Ps：one:程序的数据存储均是从下标1开始的。 two:以下程序均是升序。

直接插入排序（O() 稳定排序）

思路：插入排序是一种比较容易想到的算法，它的思路有点向我们打扑克时排列手牌的操作。比如我们要把手中的牌从左至右，从小到大进行排序。此时只需要将牌一张张抽出来，依次插入到前面已经排好的适当位置。只需重复这一操作直至插入最后一张牌，排序就已经完成了。（注意：二分中的写法，使high所指的值为小于或等于未排序顺序表中的第一个数）

code one(伪代码)

void InsertSort(int a[], int len) //len为元素个数 { int i, j, v; for(int i=2; i<=len; i++)
    {
        v = a[i]; //取出未排序部分开头的元素赋值给变量v j = i - 1; while(j>1 && a[j]>v) //在已排序部分，将所有比v大的元素向后移动一个单位 {
            a[j+1] = a[j];
            j--;
        }
        a[j+1] = v; //将已取出的元素v插入空位 }
}

code two（顺序表实现）

#include <bits/stdc++.h> using namespace std; const int MAXN = (int)1e4+10; int n; typedef struct { int key; char *otherinfo;
}ElemType; typedef struct { ElemType *elem; int length;
}SqList; void GetData(SqList &L) {
    L.length = 0; for(int i=1; i<=n; i++)
    { scanf("%d",&L.elem[i].key);
        L.length++;
    }

} void InsertSort(SqList &L) { int i, j, v; for(i=2; i<=n; i++)
    {
        L.elem[0] = L.elem[i];
        j = i - 1; while(j>=1 && L.elem[0] < L.elem[j].key)
        {
            L.elem[j+1] = L.elem[j];
            j--;
        }
        L.elem[j+1] = L.elem[0];
    }
} void print(SqList L) { for(int i=1; i<=L.length; i++) printf("%d ",L.elem[i].key);
} int main() { cin>> n;
    SqList L;
    L.elem = new ElemType[MAXN];
    GetData(L);
    InsertSort(L);
    print(L); return 0;
}

折半插入排序（O() 稳定排序）

上面的直接插入排序采用顺序查找法查找当前未排序部分的首个元素可以插入的[适当]位置，这个查找过程可以用二分查找来实现，剩下的是和直接插入排序相同的。

code one(伪代码)

void BInsertSort(int a[], int len) { int i, j, v; for(i=2; i<=len; i++)
    {
        v = a[i]; int low = 1, high = i-1, mid; //置查询区间初值， while(low<=high) //在已经排好序的序列二分查找可以插入的位置 {
            mid = (low+high)>>1; //二分 if(a[mid]>v) high = mid - 1; //插入点在前一子表 else low = mid + 1; //插入点再后一子表 } for(j=i-1; j>=high+1; j--) a[j+1] = a[j]; //记录后移 a[high+1] = v; //插入到合适位置 }
}

code two(顺序表实现)

#include <bits/stdc++.h> using namespace std; const int MAXN = (int)1e4+10; int n; typedef struct { int key; char *otherinfo;
}ElemType; typedef struct { ElemType *elem; int length;
}SqList; void GetData(SqList &L) {
    L.length = 0; for(int i=1; i<=n; i++)
    { scanf("%d",&L.elem[i].key);
        L.length++;
    }
} void BInsertSort(SqList &L) { int i, j; for(i=2; i<=n; i++)
    {
        L.elem[0] = L.elem[i]; int low = 1, high = i-1, mid; while(low<=high)
        {
            mid = (low+high)>>1; if(L.elem[mid].key>L.elem[0].key) high = mid - 1; else low = mid + 1;
        } for(j=i-1; j>=high+1; j--) L.elem[j+1] = L.elem[j];
        L.elem[high+1] = L.elem[0];
    }
} void print(SqList L) { for(int i=1; i<=L.length; i++) printf("%d ",L.elem[i].key);
} int main() { cin>> n;
    SqList L;
    L.elem = new ElemType[MAXN];
    GetData(L);
    BInsertSort(L);
    print(L); return 0;
}

希尔排序(O(n* ) 不稳定排序)

希尔排序又称“缩小增量排序”，该排序是在简单插入排序基础上进一步改进而得到的算法。

实现该算法的核心：InsertionSort(A,n,g)是仅以间隔为g的元素为对象进行的插入排序。

ShellSort(A,n)则是以InsertionSort(A,n,g)的循环，并且在每轮循环后逐渐缩小g的范围。

插入排序法可以高速处理顺序较整齐的数据，而希尔排序法就是充分发挥这一特长的高速算法。

code one

#include <bits/stdc++.h> using namespace std; const int MAXN = (int)1e5+10; int a[MAXN]; vector<int> G; void GetData(int f[], int len) { int i; for(i=1; i<=len; i++) scanf("%d",&a[i]);
} void Print(int a[],int len) { int i; for(int i=1; i<=len; i++) printf("%d ",a[i]);
} void InsertionSort(int a[], int len, int g)//仅以间隔为g的元素为对象进行插入排序 { for(int i=g; i<=len; i++)
    { int v = a[i]; int j = i - g; while(j>=1 && a[j]>v)
        {
            a[j+g] = a[j];
            j -= g;
        }
        a[j+g] = v;
    }
} void ShellSort(int a[],int len) { //生成数列G = {1,4,13,40,121,364,1093,,,} for(int h = 1; ; )
    { if(h>len) break;
        G.push_back(h);
        h = 3*h+1;
    } int t = G.size() - 1; for(int i=t; i>=0; i--) InsertionSort(a,len,G[i]);
} int main() { int n; cin>> n;
    GetData(a,n);
    ShellSort(a,n);
    Print(a,n); return 0;
}

code two（顺序表实现）

#include <bits/stdc++.h> using namespace std; const int MAXN = (int)1e4+10; int n; vector<int> G; typedef struct { int key; char *otherinfo;
}ElemType; typedef struct { ElemType *elem; int length;
}SqList; void GetData(SqList &L) {
    L.length = 0; for(int i=1; i<=n; i++)
    { scanf("%d",&L.elem[i].key);
        L.length++;
    }
} void print(SqList L) { for(int i=1; i<=L.length; i++) printf("%d ",L.elem[i].key);
} void InsertionSort(SqList &L, int len, int g) { for(int i=g; i<=len; i++)
    {
        ElemType v = L.elem[i]; int j = i-g; while(j>=1 && L.elem[j].key > v.key)
        {
            L.elem[j+g] = L.elem[j];
            j = j - g;
        }
        L.elem[j+g] = v;
    }
} void ShellSort(SqList &L, int len) { for(int h=1; ;)
    { if(h>len) break;
        G.push_back(h);
        h = 3*h+1;
    } int t = G.size() - 1; for(int i=t; i>=0; i--) InsertionSort(L,len,G[i]);
} int main() { cin>> n;
    SqList L;
    L.elem = new ElemType[MAXN];
    GetData(L);
    ShellSort(L,L.length);
    print(L); return 0;
}

冒泡排序（O()稳定排序）

冒泡排序是一种最简单的交换排序方法。它通过两两比较相邻的关键字，如果发生逆序，则进行交换，从而使关键字小的记录“漂浮”，或者使关键字较大的“坠落”。

算法核心：从数组尾端a[n]开始依次向前遍历,将相邻的两个进行比较，较小的排在前面。这样遍历到最前面时，则最小的数据冒出。循环进行该操作，使已排序部分增加，未排序部分减少。设置flag标志的意义在于:若进行一次从后到前的遍历后，若无数据进行交换，则证明该组数据已经排序完毕。

冒泡排序法对相邻的元素进行比较和交换，因此键值相同的元素不会改变顺序，所以冒泡排序是一种稳定的排序算法。但注意：如果将比较运算改为a[j]<=a[j-1],就会失去稳定性。

PS:冒泡排序算法中的交换次数又称为反序数或逆序数，可以体现数列的混乱程度。

code one(伪代码)

void BubbleSort(int a[], int len) { bool flag = true; for(int i=1; flag; i++)
    {
        flag = false; for(int j=len; j>i; j--)
        { if(a[j]<a[j-1]) 
            {
                swap(a[j],a[j-1]);
                flag = true;
            }
        }
    }
}

code two（顺序表实现）

#include <bits/stdc++.h> using namespace std; const int MAXN = (int)1e4+10; int n; vector<int> G; typedef struct { int key; char *otherinfo;
}ElemType; typedef struct { ElemType *elem; int length;
}SqList; void GetData(SqList &L) {
    L.length = 0; for(int i=1; i<=n; i++)
    { scanf("%d",&L.elem[i].key);
        L.length++;
    }
} void print(SqList L) { for(int i=1; i<=L.length; i++) printf("%d ",L.elem[i].key);
} void BubbleSort(SqList &L, int len) { bool flag = true; for(int i=1; flag; i++)
    {
        flag = false; for(int j=n; j>i; j--)
        { if(L.elem[j].key<L.elem[j-1].key)
            {
                swap(L.elem[j],L.elem[j-1]);
                flag = true;
            }
        }
    }
} int main() { cin>> n;
    SqList L;
    L.elem = new ElemType[MAXN];
    GetData(L);
    BubbleSort(L,L.length);
    print(L);
}

快速排序（O(nlogn)）

code one(伪代码)

void QuickSort(int a[], int st, int ed) { if(st>=ed-1) return ; int low = st; int high = ed; int val = a[low]; while(low<high)
    { while(low<high)
        { if(a[high]<=val)
            {
                a[low++] = a[high]; break;
            }
            --high;
        } while(low<high)
        { if(a[low]>=val)
            {
                a[high--] = a[low]; break;
            }
            ++low;
        }
    }
    a[low] = val;
    QuickSort(a, st, low);
    QuickSort(a, high+1, ed);
}

简单选择排序（O()不稳定排序）

选择排序算法是一种非常直观的排序算法，又被称为直接选择排序。

算法核心：每遍历一趟，选出未排序部分的最小值放在已排序的最大值的后面。直至未排序部分长度为0.

code one(伪代码)

void SelectionSort(int a[], int len) { int minj; for(int i=1; i<len; i++)
    {
        minj = i; for(int j=i+1; j<=len; j++)
        { if(a[minj]>a[j]) minj = j;
        } if(i!=minj) swap(a[i],a[minj]);
    }
}

code two(顺序表实现)

#include <bits/stdc++.h> using namespace std; const int MAXN = (int)1e4+10; int n; vector<int> G; typedef struct { int key; char *otherinfo;
}ElemType; typedef struct { ElemType *elem; int length;
}SqList; void GetData(SqList &L) {
    L.length = 0; for(int i=1; i<=n; i++)
    { scanf("%d",&L.elem[i].key);
        L.length++;
    }
} void print(SqList L) { for(int i=1; i<=L.length; i++) printf("%d ",L.elem[i].key);
} void SelectionSort(SqList &L, int len) { int minj; for(int i=1; i<len; i++)
    {
        minj = i; for(int j=i+1; j<=len; j++)
        { if(L.elem[minj].key>L.elem[j].key) minj = j;
        } if(i!=minj) swap(L.elem[i],L.elem[minj]);
    }
} int main() { cin>> n;
    SqList L;
    L.elem = new ElemType[MAXN];
    GetData(L);
    SelectionSort(L,L.length);
    print(L);
}