冒泡排序，穩定，復雜度n*n
選擇排序，不穩定，復雜度n*n
不穩定：
快速排序，遞歸實現，不穩定，復雜度n*log(n)，空間復雜度
堆排序，大小頂堆實現，不穩定，復雜度n*log(n)
穩定：
在快速排序中添加另外一個控制變量
合並排序，兩個有序隊列合並
1、快速排序示例
[cpp]
//快速排序示例
#include <cstdio>
#include <cstdlib>
int p[50];
int len;
void input()
{
len = 20;
int i;
for(i = 0; i < len; ++ i)
p[i] = rand() / 100;
p[0] = p[1] = p[2] = 50;
}
void print()
{
int i;
for(i = 0; i < len; ++ i)
printf("%d ", p[i]);
printf("\n");
}
void fsort(int l, int r)//快速排序
{
if(l >= r)
return;
int temp = p[l];
int pl, pr;
for(pl = l, pr = r;pl < pr;)
{
for(;pl < pr;)
{
if(p[pr] >= temp)
pr --;
else
break;
}
if(pl < pr) p[pl ++] = p[pr];
for(;pl < pr;)
{
if(p[pl] <= temp)
pl ++;
else
break;
}
if(pl < pr) p[pr --] = p[pl];
}
p[pr] = temp;
fsort(l, pr - 1);
fsort(pr + 1, r);
}
int main()
{
input();
print();
fsort(0, len - 1);
print();
return 0;
}
//快速排序示例
#include <cstdio>
#include <cstdlib>
int p[50];
int len;
void input()
{
len = 20;
int i;
for(i = 0; i < len; ++ i)
p[i] = rand() / 100;
p[0] = p[1] = p[2] = 50;
}
void print()
{
int i;
for(i = 0; i < len; ++ i)
printf("%d ", p[i]);
printf("\n");
}
void fsort(int l, int r)//快速排序
{
if(l >= r)
return;
int temp = p[l];
int pl, pr;
for(pl = l, pr = r;pl < pr;)
{
for(;pl < pr;)
{
if(p[pr] >= temp)
pr --;
else
break;
}
if(pl < pr) p[pl ++] = p[pr];
for(;pl < pr;)
{
if(p[pl] <= temp)
pl ++;
else
break;
}
if(pl < pr) p[pr --] = p[pl];
}
p[pr] = temp;
fsort(l, pr - 1);
fsort(pr + 1, r);
}
int main()
{
input();
print();
fsort(0, len - 1);
print();
return 0;
}
2、堆排序示例
[cpp]
/堆排序示例
#include <cstdio>
#include <cstdlib>
int p[50];
int len;
void input()
{
len = 25;
int i;
for(i = 1; i <= len; ++ i)
p[i] = rand() / 100;
p[1] = p[2] = 50;
}
void print()
{
int i;
for(i = 1; i <= len; ++ i)
printf("%d ", p[i]);
printf("\n");
}
void swap(int x, int y)
{
int temp = p[x];
p[x] = p[y];
p[y] = temp;
}
void fsort()//堆排序
{
int i;
int q;
for(i = len / 2; i >= 1; -- i)//小頂堆初始化
{
q = i;
while(2 * q <= len)
{
if(2 * q + 1 > len)
{
if(p[q] > p[2 * q])
{
swap(q, 2 * q);
q = 2 * q;
}
break;
}
else
{
if(p[2 * q] <= p[2 * q + 1])
{
if(p[q] > p[2 * q])
{
swap(q, 2 * q);
q = 2 * q;
}
else
break;
}
else
{
if(p[q] > p[2 * q + 1])
{
swap(q, 2 * q + 1);
q = 2 * q + 1;
}
else
break;
}
}
}
}
int n = 1;
while(n < len)//每次第一個數與最後一位數交換，這樣循環len - 1遍，數組從大到小排序
{
swap(len - n + 1, 1);
q = 1;
while(2 * q < len - n + 1)
{
if(2 * q + 1 >= len - n + 1)
{
if(p[q] > p[2 * q])
{
swap(q, 2 * q);
q = 2 * q;
}
else
break;
}
else
{
if(p[2 * q] <= p[2 * q + 1])
{
if(p[q] > p[2 * q])
{
swap(q, 2 * q);
q = 2 * q;
}
else
break;
}
else
{
if(p[q] > p[2 * q + 1])
{
swap(q, 2 * q + 1);
q = 2 * q + 1;
}
else
break;
}
}
}
n ++;
}
}
int main()
{
input();
print();
fsort();
print();
return 0;
}
//堆排序示例
#include <cstdio>
#include <cstdlib>
int p[50];
int len;
void input()
{
len = 25;
int i;
for(i = 1; i <= len; ++ i)
p[i] = rand() / 100;
p[1] = p[2] = 50;
}
void print()
{
int i;
for(i = 1; i <= len; ++ i)
printf("%d ", p[i]);
printf("\n");
}
void swap(int x, int y)
{
int temp = p[x];
p[x] = p[y];
p[y] = temp;
}
void fsort()//堆排序
{
int i;
int q;
for(i = len / 2; i >= 1; -- i)//小頂堆初始化
{
q = i;
while(2 * q <= len)
{
if(2 * q + 1 > len)
{
if(p[q] > p[2 * q])
{
swap(q, 2 * q);
q = 2 * q;
}
break;
}
else
{
if(p[2 * q] <= p[2 * q + 1])
{
if(p[q] > p[2 * q])
{
swap(q, 2 * q);
q = 2 * q;
}
else
break;
}
else
{
if(p[q] > p[2 * q + 1])
{
swap(q, 2 * q + 1);
q = 2 * q + 1;
}
else
break;
}
}
}
}
int n = 1;
while(n < len)//每次第一個數與最後一位數交換，這樣循環len - 1遍，數組從大到小排序
{
swap(len - n + 1, 1);
q = 1;
while(2 * q < len - n + 1)
{
if(2 * q + 1 >= len - n + 1)
{
if(p[q] > p[2 * q])
{
swap(q, 2 * q);
q = 2 * q;
}
else
break;
}
else
{
if(p[2 * q] <= p[2 * q + 1])
{
if(p[q] > p[2 * q])
{
swap(q, 2 * q);
q = 2 * q;
}
else
break;
}
else
{
if(p[q] > p[2 * q + 1])
{
swap(q, 2 * q + 1);
q = 2 * q + 1;
}
else
break;
}
}
}
n ++;
}
}
int main()
{
input();
print();
fsort();
print();
return 0;
}
3、歸並排序
[cpp]
/歸並排序示例
#include <cstdio>
#include <cstdlib>
#include <cstring>
int p[50];
int _p[50];
int len;
void input()
{
len = 20;
int i;
for(i = 0; i < len; ++ i)
_p[i] = p[i] = rand() / 100;
_p[0] = p[0] = 50;
_p[1] = p[1] = 50;
_p[2] = p[2] = 50;
}
void print()
{
int i;
for(i = 0; i < len; ++ i)
printf("%d ", p[i]);
printf("\n");
}
void fsort(int l, int r)//歸並排序
{
if(l == r)
return;
int mid = (l + r) / 2;
fsort(l, mid);
fsort(mid + 1, r);
int i, j, z;
for(i = l, j = mid + 1, z = 0; i <= mid || j <= r;)//對兩個有序數組進行排序
{
if(i > mid)
_p[l + (z ++)] = p[j ++];
else if(j > r)
_p[l + (z ++)] = p[i ++];
else
{
if(p[i] <= p[j])
_p[l + (z ++)] = p[i ++];
else
_p[l + (z ++)] = p[j ++];
}
}
//memcpy(p, _p, sizeof(_p));
for(i = l; i <= r; ++ i)
p[i] = _p[i];
}
int main()
{
input();
print();
fsort(0, len - 1);
print();
return 0;
}
