拓展排序

归并排序

归并排序采用分治的思想：

• Divide: 将n个元素平均划分为各含n/2个元素的子序列。
• Conquer:递归解决两个规模为n/2的子问题。
• Combine:合并俩个已排序的子序列。
  性能：时间复杂度为O(nlogn),空间复杂度为O（N），算法与初始序列无关，排序是稳定的。

void mergeSort(int arr[], int len) {
   int* a = arr;
   int* b = (int*) malloc(len * sizeof(int));

   for (int size = 1; size < len; size += size) {
       for (int start = 0; start < len; start += size + size) {
           int k = start;
           int left = start, right = min(left + size + size, len), mid = min(left + size, len);

           int start1 = left, end1 = mid;
           int start2 = mid, end2 = right;

           while (start1 < end1 && start2 < end2) {
               b[k++] = a[start1] > a[start2] ? a[start2++] : a[start1++];
           }

           while (start1 < end1) {
               b[k++] = a[start1++];
           }
           while (start2 < end2) {
               b[k++] = a[start2++];
           }
       }
       int* temp = a;
       a = b;
       b = temp;
   }

   if (a != arr) {
       for (int i = 0; i < len; ++i) {
           b[i] = a[i];
       }
       b = a;
   }

   free(b);
}

基数排序
对于有d个关键字时，可以分别按关键字进行排序。有两种方法：

• MSD:先从高位开始进行排序，在每个关键字上，可采用基数排序。
• LSD:先人低位开始进行排序，在每个关键字上，可采用桶排序。
  即通过每个数的每位数字的大小来比较

//找出最大数字的位数
int maxNum(int arr[], int len) {
    int _max = 0;

    for (int i = 0; i < len; ++i) {
        int d = 0;
        int a = arr[i];

        while (a) {
            a /= 10;
            d++;
        }

        if (_max < d) {
            _max = d;
        }
    }
    return _max;
}


void radixSort(int *arr, int len) {
    int d = maxNum(arr, len);
    int *temp = new int[len];
    int count[10];
    int radix = 1;

    for (int i = 0; i < d; ++i) {
        for (int j = 0; j < 10; ++j) {
            count[j] = 0;
        }

        for (int k = 0; k < len; ++k) {
            count[(arr[k] / radix) % 10]++;
        }

        for (int l = 1; l < 10; ++l) {
            count[l] += count[l - 1];
        }

        for (int m = 0; m < len; ++m) {
            int index = (arr[m] / radix) % 10;
            temp[count[index] - 1] = arr[m];
            count[index]--;
        }

        for (int n = 0; n < len; ++n) {
            arr[n] = temp[n];
        }
        radix *= 10;

    }

    delete (temp);
}

拓扑排序

在有向图中找拓扑序列的过程，就是排外排序。 ** 拓扑序列常常用于判定图是否有环 **。

• 从有向图中选择一个入度为0的结点，输出它。
• 将这个结点以及该结点出发的所有边从图中删除。
• 重复前两步，直到没有入度为0的点。

如果 所有的点都被输出，即存在一个拓扑序列，则图没有环。