|
堆排序：
void HeapAdjust(int *array, int parent, int length){
int temp = array[parent]; // temp保存当前父节点
int child = 2 * parent + 1; // 先获得左孩子
while (child < length) {
// 如果有右孩子结点，并且右孩子结点的值大于左孩子结点，则选取右孩子结点
if (child + 1 < length && array[child] < array[child + 1]) {
child++;
}
// 如果父结点的值已经大于孩子结点的值，则直接结束
if (temp >= array[child])
break;
// 把孩子结点的值赋给父结点
array[parent] = array[child];
// 选取孩子结点的左孩子结点,继续向下筛选
parent = child;
child = 2 * child + 1;
}
array[parent] = temp;
}
void heapSort(int list[], int length) {
// 循环建立初始堆
for (int i = length / 2; i >= 0; i--) {
HeapAdjust(list, i, length);
}
// 进行n-1次循环，完成排序
for (int i = length - 1; i > 0; i--) {
// 最后一个元素和第一元素进行交换
int temp = list[i];
list[i] = list[0];
list[0] = temp;
// 筛选 R[0] 结点，得到i-1个结点的堆
HeapAdjust(list, 0, i);
}
}
希尔排序：
void shell_sort(int a[], int n)
{
int d, i, j, temp; //d为增量
for(d = n/2;d >= 1;d = d/2) //增量递减到1使完成排序
{
for(i = d; i < n;i++) //插入排序的一轮
{
temp = a[i];
for(j = i - d;(j >= 0) && (a[j] > temp);j = j-d)
{
a[j + d] = a[j];
}
a[j + d] = temp;
}
}
}
快排：
int division(int list[], int left, int right) {
// 以最左边的数(left)为基准
int base = list[left];
while (left < right) {
// 从序列右端开始，向左遍历，直到找到小于base的数
while (left < right && list[right] >= base)
right--;
// 找到了比base小的元素，将这个元素放到最左边的位置
list[left] = list[right];
// 从序列左端开始，向右遍历，直到找到大于base的数
while (left < right && list[left] <= base)
left++;
// 找到了比base大的元素，将这个元素放到最右边的位置
list[right] = list[left];
}
// 最后将base放到left位置。此时，left位置的左侧数值应该都比left小；
// 而left位置的右侧数值应该都比left大。
list[left] = base;
return left;
}
void quickSort(int *list, int left, int right) {
// 左下标一定小于右下标，否则就越界了
if (left < right) {
// 对数组进行分割，取出下次分割的基准标号
int base = division(list, left, right);
// 对“基准标号“左侧的一组数值进行递归的切割，以至于将这些数值完整的排序
quickSort(list, left, base - 1);
// 对“基准标号“右侧的一组数值进行递归的切割，以至于将这些数值完整的排序
quickSort(list, base + 1, right);
}
}
计数排序：
void findArrMaxMin(int a[], int size, int *min, int *max)
{
if(size == 0) {
return;
}
if(size == 1) {
*min = *max = a[0];
return;
}
*min = a[0] > a[1] ? a[1] : a[0];
*max = a[0] <= a[1] ? a[1] : a[0];
int i, j;
for(i = 2, j = 3; i < size, j < size; i += 2, j += 2) {
int tempmax = a[i] >= a[j] ? a[i] : a[j];
int tempmin = a[i] < a[j] ? a[i] : a[j];
if(tempmax > *max)
*max = tempmax;
if(tempmin < *min)
*min = tempmin;
}
//如果数组元素是奇数个，那么最后一个元素在分组的过程中没有包含其中，
//这里单独比较
if(size % 2 != 0) {
if(a[size -1] > *max)
*max = a[size - 1];
else if(a[size -1] < *min)
*min = a[size -1];
}
}
void count_sort(int a[], int b[], int n) {
int max, min;
findArrMaxMin(a, n, &min, &max);
int numRange = max-min+1;
int* counter = new int[numRange];
int i, j, k;
for (k=0; k<numRange; k++)
counter[k]=0;
for (i=0; i<n; i++)
counter[a[i]-min]++;
for (k=1; k<numRange; k++)
counter[k] += counter[k-1];
for (j=n-1; j>=0; j--) {
int v = a[j];
int index = counter[v-min]-1;
b[index]=v;
counter[v-min]--;
}
}
桶排序：
int getNumInPos(int num,int pos) //获得某个数字的第pos位的值
{
int temp = 1;
for (int i = 0; i < pos - 1; i++)
temp *= 10;
return (num / temp) % 10;
}
#define RADIX_10 10 //十个桶，表示每一位的十个数字
#define KEYNUM 5 //整数位数
void radix_sort(int* pDataArray, int iDataNum)
{
int *radixArrays[RADIX_10]; //分别为0~9的序列空间
for (int i = 0; i < RADIX_10; i++)
{
radixArrays[i] = new int[iDataNum];
radixArrays[i][0] = 0; //index为0处记录这组数据的个数
}
for (int pos = 1; pos <= KEYNUM; pos++) //从个位开始到31位
{
for (int i = 0; i < iDataNum; i++) //分配过程
{
int num = getNumInPos(pDataArray[i], pos);
int index = ++radixArrays[num][0];
radixArrays[num][index] = pDataArray[i];
}
for (int i = 0, j =0; i < RADIX_10; i++) //写回到原数组中，复位radixArrays
{
for (int k = 1; k <= radixArrays[i][0]; k++)
pDataArray[j++] = radixArrays[i][k];
radixArrays[i][0] = 0;
}
}
}
| 
转播
