|
冒泡排序（时间复杂度N2，空间复杂度1） 依次比较数组相邻两个元素，将最大或最小元素放到后面，慢慢“浮”到数列的最后。选择排序（时间复杂度N2，空间复杂度1） 首先找到数组最小元素，将它和数组的第一个元素交换位置。再次，在剩下的元素中找到最小的元素，将它与数组第二个元素交换，如此往复。插入排序（时间复杂度介于N和N2之间，空间复杂度1）将数组分为有序和无序两个部分，默认数组左变第一个元素是有序的，依次遍历数组第二个元素到最后，与数组左变有序序列比较。如果小于左变有序序列则交换位置。希尔排序（时间复杂度NlogN，空间复杂度1） 分组+插入排序。插入排序只能交换相邻的元素，元素只能一点一点从数组的一端移动到另一端。希尔排序的思想是使数组中任意间隔为gap的数组都是有序的。经验公式：gap=gap/3+1，如果有12个元素，那么同一组元素相邻元素间隔4，下一次分组间隔2，最后一次间隔1。归并排序（时间复杂度NlogN,空间复杂度N（递归临时变量）） 将两个有序数组归并到第三个数组中，递归在发生在处理数组之后。快速排序（时间复杂度NlogN，空间复杂度lgN）） 与归并一样，都是利用分治的排序算法。将数组分成两个子数组，将两部分独立排序，递归发生在处理数组之前。不需要额外的内存空间存储一个临时数组。堆排序（时间复杂度NlogN，空间复杂度1） 利用堆（一种特殊的完全二叉树）而设计的一种排序算法。如果是正序排序，先构建一个最大堆，交换a[1]和a[n]，此时a[n]就是数组中最大元素。n–,a[1]向下调整保持最大堆特性，进行下一次交换。桶排序（时间复杂度lg(M+N)，空间复杂度N） 构建一个临时数组book，长度为要排序数组的最大值。遍历一次数组a,记录a[i]的值的次数：book[a[i]]++j.最后遍历一遍数组book，将i值和出现的数次写到数组a中。
这里是引用
#include
#include
#include
using namespace std;
//效率测试
#define NUMBER 1000000
long long getSystemTime()
{
struct timeb t;
ftime(&t);
return 1000 * t.time + t.millitm;
}
void bucketSort(int *a,int *book, int len)
{
for (int i = 0; i < len; i++)
{
int tem = a[i];
book[tem]++;
}
int k = 0;
for (int i = 0; i < NUMBER; i++)
{
int ncount = book[i];
for (int j = 0; j < ncount; j++)
{
a[k++] = i;
}
}
}
//-----------------三向切分的快速排序 ---------------------
void quick3WaySort(int *a, int left, int right)
{
if (left > right) return;
int lt = left;
int i = left + 1;
int gt = right;
int tem = a[left];
while (i tem)//大于切分元素的放在gt右边，因此gt左移
{
//exchange(a, i, gt--);
int tmp = a[i];
a[i] = a[gt];
a[gt] = tmp;
gt--;
}
else
i++;
}
quick3WaySort(a,left,lt-1);
quick3WaySort(a, gt+1, right);
}
#if 0
void quickSort(int *a, int left, int right)
{
if (left > right) return;
int i = left;
int j = right;
int tem = a[left];
while (i != j)
{
while (a[j]>tem && i |