转载自ShiLin's Bolg 数据结构排序这章内容比较经典,都是一些很好的算法,将来很可能会用得到,总结一下,加深一下印象。
文章篇幅有点大,请点击查看更多,下面是跳转链接: 一、插入排序 1)直接插入排序 2)折半插入排序 3)希尔排序 二、交换排序 1)冒泡排序 2)快速排序 三、选择排序 1)简单选择排序 2)堆排序 四、归并排序 五、基数排序
一、插入排序
1)直接插入排序 算法演示 返回目录 时间复杂度:平均情况—O(n2) 最坏情况—O(n2) 辅助空间:O(1) 稳定性:稳定 1 2 3 4 5 6 7 8 9 10 11 12 | void InsertSort(SqList &L) {
int i,j;
for (i=2; i<=L.length; ++i)
if (LT(L.r[i].key, L.r[i-1].key)) {
L.r[0] = L.r[i];
for (j=i-1; LT(L.r[0].key, L.r[j].key); --j)
L.r[j+1] = L.r[j];
L.r[j+1] = L.r[0];
}
}
|
2)折半插入排序 返回目录 时间复杂度:平均情况—O(n2) 稳定性:稳定 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | void BInsertSort(SqList &L) {
int i,j,high,low,m;
for (i=2; i<=L.length; ++i) {
L.r[0] = L.r[i];
low = 1; high = i-1;
while (low<=high) {
m = (low+high)/2;
if (LT(L.r[0].key, L.r[m].key)) high = m-1;
else low = m+1;
}
for (j=i-1; j>=high+1; --j) L.r[j+1] = L.r[j];
L.r[high+1] = L.r[0];
}
}
|
3)希尔排序 算法演示 返回目录 时间复杂度:理想情况—O(nlog2n) 最坏情况—O(n2) 稳定性:不稳定
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | void ShellInsert(SqList &L, int dk) {
int i,j;
for (i=dk+1; i<=L.length; ++i)
if (LT(L.r[i].key, L.r[i-dk].key)) {
L.r[0] = L.r[i];
for (j=i-dk; j>0 && LT(L.r[0].key, L.r[j].key); j-=dk)
L.r[j+dk] = L.r[j];
L.r[j+dk] = L.r[0];
}
}
void ShellSort(SqList &L, int dlta[], int t) {
for ( int k=0;k<t;k++)
ShellInsert(L, dlta[k]);
}
|
二、交换排序
1)冒泡排序 算法演示 返回目录 时间复杂度:平均情况—O(n2) 最坏情况—O(n2) 辅助空间:O(1) 稳定性:稳定 1 2 3 4 5 6 7 8 9 10 11 12 13 14 | void BubbleSort(SeqList R) {
int i,j;
Boolean exchange;
for (i=1;i<n;i++){ exchange= "FALSE;" j= "n-1;j" >=i;j--)
if (R[j+1].key< R[j].key){
R[0]=R[j+1];
R[j+1]=R[j];
R[j]=R[0];
exchange=TRUE;
}
if (!exchange)
return ;
}
}
|
2)快速排序 算法演示 返回目录 时间复杂度:平均情况—O(nlog2n) 最坏情况—O(n2) 辅助空间:O(log2n) 稳定性:不稳定 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 | int Partition(SqList &L, int low, int high) {
KeyType pivotkey;
RedType temp;
pivotkey = L.r[low].key;
while (low < high) {
while (low < high && L.r[high].key>=pivotkey) --high;
temp=L.r[low];
L.r[low]=L.r[high];
L.r[high]=temp;
while (low < high && L.r[low].key < =pivotkey) ++low;
temp=L.r[low];
L.r[low]=L.r[high];
L.r[high]=temp;
}
return low;
}
int Partition(SqList &L, int low, int high) {
KeyType pivotkey;
L.r[0] = L.r[low];
pivotkey = L.r[low].key;
while (low < high) {
while (low < high && L.r[high].key>=pivotkey) --high;
L.r[low] = L.r[high];
while (low < high && L.r[low].key < =pivotkey) ++low;
L.r[high] = L.r[low];
}
L.r[low] = L.r[0];
return low;
}
void QSort(SqList &L, int low, int high) {
int pivotloc;
if (low < high) {
pivotloc = Partition(L, low, high);
QSort(L, low, pivotloc-1);
QSort(L, pivotloc+1, high);
}
}
void QuickSort(SqList &L) {
QSort(L, 1, L.length);
}
|
三、选择排序
1)简单选择排序 算法演示 返回目录 时间复杂度:平均情况—O(n2) 最坏情况—O(n2) 辅助空间:O(1) 稳定性:不稳定
1 2 3 4 5 6 7 8 9 10 11 12 13 | void SelectSort(SqList &L) {
int i,j;
for (i=1; i < L.length; ++i) {
j = SelectMinKey(L, i);
if (i!=j) {
RedType temp;
temp=L.r[i];
L.r[i]=L.r[j];
L.r[j]=temp;
}
}
}
|
2)堆排序 算法演示 返回目录 时间复杂度:平均情况—O(nlog2n) 最坏情况—O(nlog2n) 辅助空间:O(1) 稳定性:不稳定 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | void HeapAdjust(HeapType &H, int s, int m) {
int j;
RedType rc;
rc = H.r[s];
for (j=2*s; j < =m; j*=2) {
if (j < m && H.r[j].key < H.r[j+1].key) ++j;
if (rc.key >= H.r[j].key) break ;
H.r[s] = H.r[j]; s = j;
}
H.r[s] = rc;
}
void HeapSort(HeapType &H) {
int i;
RedType temp;
for (i=H.length/2; i>0; --i)
HeapAdjust ( H, i, H.length );
for (i=H.length; i>1; --i) {
temp=H.r[i];
H.r[i]=H.r[1];
H.r[1]=temp;
HeapAdjust(H, 1, i-1);
}
}
|
四、归并排序 算法演示 返回目录 时间复杂度:平均情况—O(nlog2n) 最坏情况—O(nlog2n) 辅助空间:O(n) 稳定性:稳定
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | void Merge (RedType SR[], RedType TR[], int i, int m, int n) {
int j,k;
for (j=m+1, k=i; i < =m && j < =n; ++k) {
if LQ(SR[i].key,SR[j].key) TR[k] = SR[i++];
else TR[k] = SR[j++];
}
if (i < =m)
while (k < =n && i < =m) TR[k++]=SR[i++];
if (j < =n)
while (k < =n &&j < =n) TR[k++]=SR[j++];
}
void MSort(RedType SR[], RedType TR1[], int s, int t) {
int m;
RedType TR2[20];
if (s==t) TR1[t] = SR[s];
else {
m=(s+t)/2;
MSort(SR,TR2,s,m);
MSort(SR,TR2,m+1,t);
Merge(TR2,TR1,s,m,t);
}
}
void MergeSort(SqList &L) {
MSort(L.r, L.r, 1, L.length);
}
|
五、基数排序 算法演示 返回目录 时间复杂度:平均情况—O(d(n+rd)) 最坏情况—O(d(n+rd)) 辅助空间:O(rd) 稳定性:稳定 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 | void Distribute(SLList &L, int i, ArrType &f, ArrType &e) {
int j, p;
for (j=0; j < RADIX; ++j) f[j] = 0;
for (p=L.r[0].next; p; p=L.r[p].next) {
j = L.r[p].keys[i]- '0' ;
if (!f[j]) f[j] = p;
else L.r[e[j]].next = p;
e[j] = p;
}
}
void Collect(SLList &L, int i, ArrType f, ArrType e) {
int j,t;
for (j=0; !f[j]; j++);
L.r[0].next = f[j];
t = e[j];
while (j < RADIX) {
for (j=j+1; j < RADIX && !f[j]; j++);
if (j < RADIX)
{ L.r[t].next = f[j]; t = e[j]; }
}
L.r[t].next = 0;
}
void RadixSort(SLList &L) {
int i;
ArrType f, e;
for (i=1; i < L.recnum; ++i) L.r[i-1].next = i;
L.r[L.recnum].next = 0;
for (i=0; i < L.keynum; ++i) {
Distribute(L, i, f, e);
Collect(L, i, f, e);
print_SLList2(L, i);
}
}
|
|