1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

void Insertsort2(int a[], int n)
{
    int i, j;
    for (i = 1; i < n; i++)
        if (a[i] < a[i - 1])
        {
            int temp = a[i];
            for (j = i - 1; j >= 0 && a[j] > temp; j--)
                a[j + 1] = a[j];
            a[j + 1] = temp;
        }
}

1
2
3
4
5
6
7

void Insertsort3(int a[], int n)
{
    int i, j;
    for (i = 1; i < n; i++)
        for (j = i - 1; j >= 0 && a[j] > a[j + 1]; j--)
            Swap(a[j], a[j + 1]);
}

1
2
3
4
5
6
7
8

void shellsort3(int a[], int n)
{
    int i, j, gap;
    for (gap = n/3 + 1; gap > 0; gap = gap / 3 + 1)  //确定gap
        for (i = gap; i < n; i++)  //扫描数组，枚举比较元素
            for (j = i - gap; j >= 0 && a[j] > a[j + gap]; j -= gap)//扫描之前的同组元素
                Swap(a[j], a[j + gap]);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

void Selectsort(int a[], int n)
{
    int i, j, nMinIndex;
    for (i = 0; i < n; i++)
    {
        nMinIndex = i; //找最小元素的位置
        for (j = i + 1; j < n; j++)
            if (a[j] < a[nMinIndex])
                nMinIndex = j;

        Swap(a[i], a[nMinIndex]); //将这个元素放到无序区的开头
    }
}

1
2
3
4
5
6
7
8
9

inline int parent(int idx) {//父节点
    return (idx >> 1);
}
inline int left(int idx) {//左孩子
    return (idx << 1) + 1;
}
inline int right(int idx) {//右孩子
    return (idx << 1) + 2;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

void max_heapify(vector<int>& nums, int idx,int n) {//检查i节点是否满足性质
    int largest = idx;//largest保持最大节点的下标
    int l = left(idx), r = right(idx);
    //注意左右孩子保证不越界
    if (l < n && nums[l] > nums[largest]) largest = l;
    if (r < n && nums[r] > nums[largest]) largest = r;
    if (largest != idx) {//需要进行维护
        swap(nums[idx], nums[largest]);
        max_heapify(nums, largest,n);//递归向下调整
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

void max_heapify(vector<int>& nums, int idx,int n) {//检查i节点是否满足性质
    int largest = idx;//largest保持最大节点的下标
    int l=left(idx);//先求出左孩子的位置，方便判断是否到达下沉终点。
    while(l<n){//仍有孩子节点
        int r = right(idx);
        //注意左右孩子保证不越界
        if (l < n && nums[l] > nums[largest]) largest = l;
        if (r < n && nums[r] > nums[largest]) largest = r;
        if (largest == idx) {//不需要进行维护
            break;
        }
        swap(nums[idx], nums[largest]);
        idx=largest;
        l=left(idx);
    }
}

1
2
3
4
5
6

void build_max_heap(vector<int>& nums) {
    heap_size = nums.size();
    for (int i = (heap_size >> 1) - 1; i >= 0; i--)
    //(heap_size >> 1) - 1最后一个父节点
        max_heapify(nums, i);
}

1
2
3
4
5
6
7
8
9

void heapsort(vector<int>& nums, int k) {
    build_max_heap(nums);
    int n=nums.size();
    for (int i = 0; i < k; i++) {
        swap(nums[0], nums[n-1]);
        n--;
        max_heapify(nums, 0,n);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

int maxheapinsert(int *heap, int n, int num)
{
    int i, j;
    heap[n] = num;//num插入堆尾
    i = n;
    j = parent(i);//j指向i的父结点

    //注意不要漏掉i!=0的条件。因为必须保证i有父结点j。j>=0并不能保证i!=0。
    //如果没有此条件，当i=0时，j=0,若heap[0]<num,程序就会陷入死循环。
    while (j >= 0 && i != 0)
    {
        if (heap[j] >= num)//当i的父节点比num大的时候，i就是num该放的位置
            break;
        heap[i] = heap[j];//类似插入排序，将j位的元素换到i位。
        i = j;
        j = (i - 1) / 2;
    }
    heap[i] = num;
    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

int maxheapinsert(int *heap, int n, int num)
{
    int i, j;
    heap[n] = num;//num插入堆尾
    i = n;
    j = parent(i);//j指向i的父结点
    for (int j = (i - 1) / 2;
            (j >= 0 && i != 0)&& a[i] < a[j];
            i = j, j = (i - 1) / 2)
        Swap(a[i], a[j]);
}

1
2
3
4
5
6
7
8

int heapextractmax(int *heap, int n)
{
//使用堆尾元素直接覆盖堆顶元素。
heap[0] = heap[n - 1];
//从堆顶到堆尾(此时堆中只有n-1个元素)进行堆调整。
max_heapify(nums, i,n-1);
return 0;
}

1
2
3
4
5
6
7
8
9

//冒泡排序1
void BubbleSort1(int a[], int n)
{
   int i, j;
   for (i = 0; i < n; i++)
          for (j = 1; j < n - i; j++)
                 if (a[j - 1] > a[j])
                        Swap(a[j - 1], a[j]);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

//冒泡排序2
void BubbleSort2(int a[], int n)
{
       int j, k;
       bool flag;

       k = n;
       flag = true;
       while (flag)
       {
              flag = false;
              for (j = 1; j < k; j++)
                     if (a[j - 1] > a[j])
                     {
                            Swap(a[j - 1], a[j]);
                            flag = true;
                     }
              k--;
       }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

//冒泡排序3
void BubbleSort3(int a[], int n)
{
    int j, k;
    int flag;

    flag = n;
    while (flag > 0)
    {
        k = flag;
        flag = 0;
        for (j = 1; j < k; j++)
            if (a[j - 1] > a[j])
            {
                Swap(a[j - 1], a[j]);
                flag = j;
            }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

void quick_sort(int s[], int l, int r)
{
    if (l < r)//partion步骤
    {
        int i = l, j = r, x = s[l];  //s[l]即s[i]就是第一个坑
        while (i < j)
        {
            while(i < j && s[j] >= x) // 从右向左找第一个小于x的数
                j--;
            if(i < j)    //将s[j]填到s[i]中，s[j]就形成了一个新的坑
                s[i++] = s[j];

            while(i < j && s[i] < x) // 从左向右找第一个大于等于x的数
                i++;
            if(i < j)   //将s[i]填到s[j]中，s[i]就形成了一个新的坑
                s[j--] = s[i];
        }
        s[i] = x;
        quick_sort(s, l, i - 1); // 递归调用
        quick_sort(s, i + 1, r);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

void MemeryArray(int a[], int n, int b[], int m, int c[])
{
    int i, j, k;

    i = j = k = 0;
    while (i < n && j < m)
    {
        if (a[i] < b[j])
            c[k++] = a[i++];
        else
            c[k++] = b[j++];
    }

    while (i < n)
        c[k++] = a[i++];

    while (j < m)
        c[k++] = b[j++];
}

 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

//将有二个有序数列a[first...mid]和a[mid...last]合并。
void mergearray(int a[], int first, int mid, int last, int temp[])
{
    int i = first, j = mid + 1;
    int m = mid,   n = last;
    int k = 0;

    while (i <= m && j <= n)
    {
        if (a[i] <= a[j])
            temp[k++] = a[i++];
        else
            temp[k++] = a[j++];
    }

    while (i <= m)
        temp[k++] = a[i++];

    while (j <= n)
        temp[k++] = a[j++];

    for (i = 0; i < k; i++)
        a[first + i] = temp[i];
}
void mergesort(int a[], int first, int last, int temp[])
{
    if (first < last)
    {
        int mid = (first + last) / 2;
        mergesort(a, first, mid, temp);    //左边有序
        mergesort(a, mid + 1, last, temp); //右边有序
        mergearray(a, first, mid, last, temp); //再将二个有序数列合并
    }
}

bool MergeSort(int a[], int n)
{
    int *p = new int[n];
    if (p == NULL)
        return false;
    mergesort(a, 0, n - 1, p);
    delete[] p;
    return true;
}

 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

int GetNumInPos(int num,int pos)  //找到num的从低到高的第pos位的数据
{
    int temp = 1;
    for (int i = 0; i < pos - 1; i++)
        temp *= 10;

    return (num / temp) % 10;
}

#define RADIX_10 10    //整型排序
#define KEYNUM_31 10     //关键字个数，这里为整型位数
void RadixSort(int* pDataArray, int iDataNum)
{
    int *radixArrays[RADIX_10];    //分别为0~9的序列空间
    for (int i = 0; i < 10; i++)
    {
        radixArrays[i] = (int *)malloc(sizeof(int) * (iDataNum + 1));
        radixArrays[i][0] = 0;    //index为0处记录这组数据的个数
    }

    for (int pos = 1; pos <= KEYNUM_31; 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++)    //收集
        {
            for (int k = 1; k <= radixArrays[i][0]; k++)
                pDataArray[j++] = radixArrays[i][k];
            radixArrays[i][0] = 0;    //复位
        }
    }
}

 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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

#include<iostream>
#include<malloc.h>
using namespace std;
int getdigit(int x,int d)
{
    int a[] = {1, 1, 10};     //因为待排数据最大数据也只是两位数，所以在此只需要到十位就满足
    return ((x / a[d]) % 10);    //确定桶号
}
void  PrintArr(int ar[],int n)
{
    for(int i = 0; i < n; ++i)
        cout<<ar[i]<<" ";
    cout<<endl;
}
void msdradix_sort(int arr[],int begin,int end,int d)
{
    const int radix = 10;
    int count[radix], i, j;
    //置空
    for(i = 0; i < radix; ++i)
    {
        count[i] = 0;
    }
    //分配桶存储空间
    int *bucket = (int *) malloc((end-begin+1) * sizeof(int));
    //统计各桶需要装的元素的个数
    for(i = begin;i <= end; ++i)
    {
        count[getdigit(arr[i], d)]++;
    }
    //求出桶的边界索引，count[i]值为第i个桶的右边界索引+1
    for(i = 1; i < radix; ++i)
    {
        count[i] = count[i] + count[i-1];
    }
    //这里要从右向左扫描，保证排序稳定性
    for(i = end;i >= begin; --i)
    {
        j = getdigit(arr[i], d);      //求出关键码的第d位的数字， 例如：576的第3位是5
        bucket[count[j]-1] = arr[i];   //放入对应的桶中，count[j]-1是第j个桶的右边界索引
        --count[j];                    //第j个桶放下一个元素的位置(右边界索引+1)
    }
    //注意：此时count[i]为第i个桶左边界
    //从各个桶中收集数据
    for(i = begin, j = 0;i <= end; ++i, ++j)
    {
        arr[i] = bucket[j];
    }
    //释放存储空间
    free(bucket);
    //对各桶中数据进行再排序
    for(i = 0;i < radix; i++)
    {
        int p1 = begin + count[i];         //第i个桶的左边界
        int p2 = begin + count[i+1]-1;     //第i个桶的右边界
        if(p1 < p2 && d > 1)
        {
            msdradix_sort(arr, p1, p2, d-1);  //对第i个桶递归调用，进行基数排序，数位降 1
        }
    }
}
void  main()
{
    int  ar[] = {12, 14, 54, 5, 6, 3, 9, 8, 47, 89};
    int len = sizeof(ar)/sizeof(int);
    cout<<"排序前数据如下："<<endl;
    PrintArr(ar, len);
    msdradix_sort(ar, 0, len-1, 2);
    cout<<"排序后结果如下："<<endl;
    PrintArr(ar, len);
}
/*
排序前数据如下：
12 14 54 5 6 3 9 8 47 89
排序后结果如下：
3 5 6 8 9 12 14 47 54 89
 */

 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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

#include<iostream>
#include<malloc.h>
using namespace std;
#define   MAXSIZE   10000
int getdigit(int x,int d)
{
    int a[] = {1, 1, 10, 100};   //最大三位数，所以这里只要百位就满足了。
    return (x/a[d]) % 10;
}
void  PrintArr(int ar[],int n)
{
    for(int i = 0;i < n; ++i)
    {
        cout<<ar[i]<<" ";
    }
    cout<<endl;
}
void lsdradix_sort(int arr[],int begin,int end,int d)
{
    const int radix = 10;
    int count[radix], i, j;
    int *bucket = (int*)malloc((end-begin+1)*sizeof(int));  //所有桶的空间开辟

    //按照分配标准依次进行排序过程
    for(int k = 1; k <= d; ++k)
    {
        //置空
        for(i = 0; i < radix; i++)
        {
            count[i] = 0;
        }
        //统计各个桶中所盛数据个数
        for(i = begin; i <= end; i++)
        {
           count[getdigit(arr[i], k)]++;
        }
        //count[i]表示第i个桶的右边界索引
        for(i = 1; i < radix; i++)
        {
            count[i] = count[i] + count[i-1];
        }
        //把数据依次装入桶(注意装入时候的分配技巧)
        for(i = end;i >= begin; --i)        //这里要从右向左扫描，保证排序稳定性
        {
            j = getdigit(arr[i], k);        //求出关键码的第k位的数字， 例如：576的第3位是5
            bucket[count[j]-1] = arr[i]; //放入对应的桶中，count[j]-1是第j个桶的右边界索引
            --count[j];               //对应桶的装入数据索引减一
        }
        //注意：此时count[i]为第i个桶左边界

        //从各个桶中收集数据
        for(i = begin,j = 0; i <= end; ++i, ++j)
        {
            arr[i] = bucket[j];
        }
    }
    free(bucket);
}
void  main()
{
    int  br[10] = {20, 80, 90, 589, 998, 965, 852, 123, 456, 789};
    cout<<"原数据如下："<<endl;
    PrintArr(br,10);
    lsdradix_sort(br, 0, 9, 3);
    cout<<"排序后数据如下："<<endl;
    PrintArr(br, 10);
}
/*
原数据如下：
20 80 90 589 998 965 852 123 456 789
排序后数据如下：
20 80 90 123 456 589 789 852 965 998
*/