重新分析几个重点排序算法

1. 快速排序

快速排序就是挖坑再填坑。一般我取最左边的那个数作为基准数temp，然后从右往左遍历数组直到找到一个数小于temp，将这个数挖出，填在基准数所在的位置，然后再从左往右找到一个大于temp，再交换。就这样不断的重复，直到排序完成。

int quickSort(int s[],int _left,int _right) 
{
    if (_left < _right)
    {
        int l = _left, r = _right, temp = s[_left];
        while (l < r)
        {
            while (l < r&&s[r] >= temp)
                r--;

            if (l < r)
                s[l++] = s[r];
            while (l < r&&s[l] < temp)
                l++;
            if (l < r)
                s[r--] = s[l];
        }
        s[l] = temp;
        quickSort(s, _left, l - 1);
        quickSort(s, l + 1, _right);
    }

}

2. 堆排序

堆排序的关键是在建堆和调整堆。
其实整个堆排序过程中, 我们只需重复做两件事：

• 建堆(初始化+调整堆, 时间复杂度为O(n));
• 拿堆的根节点和最后一个节点交换(siftdown, 时间复杂度为O(n*log n) )

下面通过一组数据说明堆排序的方法：
9, 79, 46, 30, 58, 49

1. 将排序的数视为完全二叉树（按层次进行排序）

   
   初始化
2. 判断完全二叉树的最后一个非叶子节点的左右子树是否小于它，如果小于就进行调整。最后一个节点的索引为数组长度len-1，那么最后一个非叶子节点的索引应该是为(len-1)/2.也就是从索引为2的节点开始，如果其子节点的值大于其本身的值。则把他和较大子节点进行交换，即将索引2处节点和索引5处元素交换。交换后的结果如图
   第一次比较
3. 再向前处理前一个节点，即节点1，此时79>30&&79>58，无需交换

4. 再次向前处理前一个节点，即节点0，此时9<79&&9<49，所以需要进行交换，将节点0与它的后一个节点进行交换，也就是节点1，因为79>49

   
   第二次交换
5. 如果某个节点与它的子节点交换后，它的子节点也有子节点，那么系统还需要再次对该子节点进行判断。如上图因为1处，3处，4处中，1处的值大于3,4出的值，所以还需交换。
   调整子节点的子节点

void adjust(int arr[], int len, int index)
{
    int left = 2*index + 1;
    int right = 2*index + 2;
    int maxIdx = index;
    if(left<len && arr[left] > arr[maxIdx]) maxIdx = left;
    if(right<len && arr[right] > arr[maxIdx]) maxIdx = right;  // maxIdx是3个数中最大数的下标
    if(maxIdx != index)                 // 如果maxIdx的值有更新
    {
        swap(arr[maxIdx], arr[index]);
        adjust(arr, len, maxIdx);       // 递归调整其他不满足堆性质的部分
    }

}
void heapSort(int arr[], int size)
{
    for(int i=size/2 - 1; i >= 0; i--)  // 对每一个非叶结点进行堆调整(从最后一个非叶结点开始)
    {
        adjust(arr, size, i);
    }
    for(int i = size - 1; i >= 1; i--)
    {
        swap(arr[0], arr[i]);           // 将当前最大的放置到数组末尾
        adjust(arr, i, 0);              // 将未完成排序的部分继续进行堆排序
    }
}

int main()
{
    int array[8] = {8, 1, 14, 3, 21, 5, 7, 10};
    heapSort(array, 8);
    for(auto it: array)
    {
        cout<<it<<endl;
    }
    return 0;
}

3. 基数排序

它就是桶排序的拓展，它将整数的各个位置从大到小进行排序，先对个位数进行排序，然后对十位数...，位数小的数前面补0.

排序图示

基数排序的流程

• 先获得数组的最大值计算出最大指数
• 从指数1开始根据位数对数组进行排序
• 对数组按照指数进行排序

int getMax(int a[], int n)
{
    int max=a[0];
    for (int i = 0; i < n; i++)
    {
        if (a[i]>max)
            max = a[i];
    }
    return max;
}


void countSort(int a[],  int n, int exp)
{
    vector<int> output(10);
    int i, buckets[10] = { 0 };
    //将数据出现的次数存储在buckets[]中
    for (int i = 0; i < n; i++)
        buckets[(a[i] / exp) % 10]++;
    //更改buckets[]的值，对应output的位置
    for (int i = 0; i < n; i++)
        buckets[i] += buckets[i - 1];
    //将数据存储到临时数组中
    for (int i = n - 1; i >= 0; i--)
    {
        output[buckets[(a[i] / exp) % 10] - 1] = a[i];
        buckets[(a[i] / exp) % 10]--;
    }

    // 将排序好的数据赋值给a[]
    for (i = 0; i < n; i++)
        a[i] = output[i];
}

void radixSort(int a[],  int n){
    int exp;
    int max = getMax(a, n);
    for (exp = 1; max / exp > 0; exp *= 10)
        countSort(a, n, exp);
}

4. 归并排序

归并排序的基本思想是将若干个序列进行两两归并，直至所有待排序记录都在一个有序序列为止。

归并排序

void Merge(int arr[], int reg[], int start, int end) {
    if (start >= end)return;
    int len = end - start, mid = (len >> 1) + start;

    //分成两部分
    int start1 = start, end1 = mid;
    int start2 = mid + 1, end2 = end;
    //然后合并
    Merge(arr, reg, start1, end1);
    Merge(arr, reg, start2, end2);


    int k = start;
    //两个序列一一比较,哪的序列的元素小就放进reg序列里面,然后位置+1再与另一个序列原来位置的元素比较
    //如此反复,可以把两个有序的序列合并成一个有序的序列
    while (start1 <= end1 && start2 <= end2)
        reg[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];

    //然后这里是分情况,如果arr2序列的已经全部都放进reg序列了然后跳出了循环
    //那就表示arr序列还有更大的元素(一个或多个)没有放进reg序列,所以这一步就是接着放
    while (start1 <= end1)
        reg[k++] = arr[start1++];

    //这一步和上面一样
    while (start2 <= end2)
        reg[k++] = arr[start2++];
    //把已经有序的reg序列放回arr序列中
    for (k = start; k <= end; k++)
        arr[k] = reg[k];
}

void MergeSort(int arr[], const int len) {
    //创建一个同样长度的序列,用于临时存放
    int  reg[len];
    Merge(arr, reg, 0, len - 1);
}