[数据结构与算法]DS -＞ 排序 -＞ C++实现

theory into practice. 实现各类排序方法

插入排序： 直接插入排序、折半插入排序、希尔排序
交换排序：冒泡排序、快速排序
选择排序：简单选择排序、堆排序
归并排序
基数排序

• 直接插入排序
• 折半插入排序
• 希尔排序
• 冒泡排序
• 快速排序
• 简单选择排序
• 堆排序
• 归并排序
• 基数排序

归并排序

JZ51 数组中的逆序对
解题思路：一开始使用的是两重for循环嵌套，结果5/6测试用例通过。后看到题目要求时间复杂度为$o(n\log n)$，需要对进行改进。
首先备份一下两重for循环的代码：

class Solution {
public:
    int InversePairs(vector<int> data) {
        int p = 0;
        for(vector<int>::iterator it1 = data.begin(); it1 != data.end(); it1++)
        {
            for(vector<int>::iterator it2 = it1 + 1; it2 != data.end(); it2++)
            {
                if(*it2 < *it1) p++;
            }
        }
        return p % 1000000007;
    }
};

接下来是改进方法：采用归并排序，分而治之。
思路：

1. 递归划分到最小操作区间
2. 合并，将两个操作区间合并为一个区间【用临时数组存储】，然后将临时数组赋值给最初的数组

class Solution {
public:
    long cnt;
    int InversePairs(vector<int> data)
    {
        cnt = 0;
        if(data.size() == 0) return 0;
        mergesort(data,0,data.size() - 1);
        return cnt % 1000000007;
    }
    void mergesort(vector<int>& A, int low, int high)
    {
        if(low < high)
        {
            int mid = (low + high) / 2;
            mergesort(A,low,mid);
            mergesort(A,mid+1,high);
            vector<int> tmp;
            merge(A,tmp,low,mid,high);
        }
    }
    void merge(vector<int>& A,vector<int> B,int low,int mid,int high)
    {
        int i, j;
        for(i = low, j = mid + 1; i <= mid && j <= high;)
        {
            if(A[i] > A[j]) 
            {
                B.push_back(A[j++]);
                cnt += mid - i + 1; 
            }
            else if(A[i] <= A[j]) B.push_back(A[i++]);
        }
        while(i <= mid) B.push_back(A[i++]);
        while(j <= high) B.push_back(A[j++]);
        
        int k = 0;
        for(int i = low; i <= high && k < B.size(); i++)
        {
            A[i] = B[k++];
        }
    }
    
};

难点

1. vector<int>tmp的位置，按照算法笔记的介绍来说，用来存储暂时的合并结果的数组应该在merge()函数之外
   解决方法： 加在mergesort()函数体内，递归划分到最小操作区间之后，开始merge之前
2. 计数器cnt的使用
   解决方法： 归并排序的“精髓”就是两个有序的区间合并为一个有序的区间，即：两个数组A，B，若A[i] < B[j]，则A[0], A[1] ... A[i-1]均小于B[j]。所以可用来求逆序对，若A[i]>B[j]，则有一个逆序对，cnt+1
3. “临时”向量的使用，tmp作为一个储存临时结果的容器，整个归并排序的过程需要的是这个容器，而不是容器里的内容，因此在参数传递中，不需要使用引用，即void merge(vector<int>& A,vector<int> B,int low,int mid,int high)，A需要加引用，因为是源数据，而B不需要加引用

堆排序(优先队列)

首先，放上堆排序的代码

//A[0]空着
//建立大根堆
void BuildMaxHeap(int A[],int len)
{
	for(int i = len / 2; i > 0; i--)
		HeadAdjust(A,i,len);
}

void HeadAdjust(int A[],int k, int len)
{
	A[0] = A[k];
	for(int i = 2 * k; i <= len; i *= 2) // 2 * k 是k位置元素的左孩子, i + 1 是k位置元素的右孩子
	{
		if(i < len && A[i]<A[i+1]) i++; //左右孩子中选出最大的
		if(A[0] >= A[i]) break;
		else
		{
			A[k] = A[i];
			k = i;
		}
	}
	A[k] = A[0];
}

//堆排序
void HeapSort(int A[], int len)
{
	BuildMaxHeap(A,len);
	for(int i = len; i > 1; i--)
	{
		swap(A[i],A[1]);//A[i]为堆顶
		HeadAdjust(A,1,i-1);
	}
} 

然后，是本质是堆排序的优先队列
语法见STL总结，注意：top可返回堆顶，而pop只能删除，无法得到删除的数据
具体应用：JZ40 最小的K个数

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) 
    {
        /* 优先队列解决*/
        vector<int> ans;
        if(k == 0 || k > input.size()) return ans;
        priority_queue<int,vector<int>> pri_que;
        for(const int val : input) //赋值语句 类似于for(;;)
        {
            if(pri_que.size() < k) pri_que.push(val);
            else
            {
                if(val < pri_que.top())//当前堆非最小的k个数
                {
                    pri_que.pop();
                    pri_que.push(val);
                }
            }
        }
        while(!pri_que.empty())
        {
            ans.push_back(pri_que.top());
            pri_que.pop();
        }
        return ans;
    }
};

C++中sort()函数

语法见STL总结
具体应用：JZ40 最小的K个数

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) 
    {
        /*sort()函数解决*/
        vector<int> ans;
        if(k == 0 || k > input.size()) return ans;
        sort(input.begin(),input.end());
        for(int i = 0; i < k; i++)
            ans.push_back(input[i]);
        return ans;
        
    }
};

快速排序

首先，放上算法

void QuickSort(ElemType A[], int low, int high)
{
	if(low < high)
	{
		int pivotpos = Partition(A, low, high);
		QuickSort(A, low, pivotpos - 1);
		QuickSort(A, pivotpos + 1, high);
	}
}
/*一次划分后，能够确定pivot的位置*/
int Partition(ElemType A[], int low, int high)
{
	ElemType pivot = A[low];
	while(low < high)
	{
		while(low < high && A[high] >= pivot) --high;//从后往前找到第一个比pivot小的值的位置
		A[low] = A[high];
		while(low < high && A[low] <= pivot) ++low;// 从前往后，找到第一个比pivot大的值的位置
		A[high] = A[low];
	}
	A[low] = pivot;
	return low;
}

具体应用：JZ40 最小的K个数

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) 
    {
        /*快排解决*/
        vector<int> ans;
        if(k == 0 || k > input.size()) return ans;
        QuickSort(input, 0, input.size()-1);
        for(int i = 0; i < k; i++)
            ans.push_back(input[i]);
        return ans;   
    }
    void QuickSort(vector<int>& data,int low, int high)
    {
        if(low < high)
        {
            int pivotpos = Partition(data,low,high);
            QuickSort(data, low, pivotpos - 1);
            QuickSort(data, pivotpos + 1, high);
        }
    }
    int Partition(vector<int>&data,int low, int high)
    {
        int pivot = data[low];
        while(low < high)
        {
            while(low < high && data[high] >= pivot) high--;
            data[low] = data[high];
            while(low < high && data[low] <= pivot) low++;
            data[high] = data[low];
        }
        data[low] = pivot;
        return low;
    }
};