排序

排序算法有很多，在这我先介绍冒泡排序、插入排序、归并排序、桶排序、基数排序和堆排序

冒泡排序和插入排序

  • 冒泡排序：比较相邻元素，直到序列变为有序为止
  • 插入排序：将无序的元素插入到有序的元素序列中，插入后仍然有序

    归并排序

    分治和归并

  • 分治：1、分解：将原问题分解成一系列子问题；2、解决：递归地求解各子问题。3、合并：将子问题的结果合并原问题的解。
  • 归并：关键在于归并两个相邻的子序列，使其变成一个排序好的新序列


    那么代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void merge(int arr[],int left,int mid,int right,int temp[]){
    int i = left; //左序列指针
    int j = mid + 1; //右序列指针
    int t = 0; //临时数组指针
    while(i <= mid && j <= right){
        if(arr[i] < arr[j]){
            temp[t++] = arr[i++];
        }else{
            temp[t++] = arr[j++];
        }
        while(i <= mid){
            temp[t++] = arr[i++];
        }
        while(j <= right){
            temp[t++] = arr[j++];
        }
        t = 0;
        while(left <= right){
            arr[t++] = temp[t++];
        }
    }
}
1
2
3
4
5
6
7
8
void mergesort(int arr,int left, int right, int temp[]){
   if(left < right){
       int mid = (right-left)/2 + left;
       mergesort(arr, left, mid, temp);
       mergesort(arr, mid + 1, right, temp);
       merge(arr, left, mid, right,temp);
   } 
}

也就是说归并算法，就包括了分治策略和合并。同时分治算法也是比较常用的一种算法

桶排序

  • 桶排序：将数据均匀分配到有限数量的桶中，然后对每个桶再分别排序，对每个桶再使用插入排序算法，最后将每个桶中的数据有序的组合起来。
  • 桶数量越多，时间效率越高，然而占用的空间也就越大
  1. 初始化装入连续区间元素的n个桶，每个桶用来装一段区间的元素
  2. 遍历待排序的数据，将其映射到对应的桶中，保证每个桶中的元素都在同一个区域范围中。
  3. 对每个桶进行排序，最终将所有的桶中排好序的元素连起来
    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
    //桶排序
    //b表示需要nums.size()/b个桶；
    void BucketSort(vector<int>& nums, int b=1) {
    	if (nums.size() < 2) return;
    	int maxVal = INT32_MIN;
    	int minVal = INT32_MAX;
    	for (int i = 0; i < nums.size(); ++i) {
    		maxVal = max(maxVal, nums[i]);
    		minVal = min(minVal, nums[i]);
    	}
    	int k = (maxVal - minVal + b) / b;
    	vector<vector<int>>buckets(k);
    	//分配
    	for (int i = 0; i < nums.size(); ++i) {
    		int index = (nums[i] - minVal) / b;
    		buckets[index].push_back(nums[i]);
    	}
    	int index = 0;
    	//桶内排序与收集
    	for (int i = 0; i < buckets.size(); ++i) {
    		//使用其他排序方法进行桶内排序
    		sort(buckets[i].begin(), buckets[i].end());
    		for (auto& val : buckets[i])
    			nums[index++] = val;
    	}
    }
    参考文献1
    参考文献2

    基排序

  • 基排序：假设输入数据属于一个小区间内的整数，对每一位上进行进桶，出桶；根据关键字中各位的值，通过对排序的N个元素进行若干躺“分配”与“收集”来实现排序
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    //基数排序
    void RadixSort(vector<int>&nums) {
    	//最大位数
    	int k = 0;
    	for (int i = 0; i < nums.size(); ++i) 
    		k = max(int(log(nums[i])) + 1, k);
    	for (int i = 0; i < k; ++i) {
    		//十进制
    		vector<vector<int>>radix(10);
    		//分配
    		for (int j = 0; j < nums.size(); ++j) {
    			int index = int(nums[j] / pow(10, i)) % 10;
    			radix[index].push_back(nums[j]);
    		}
    		int index = 0;
    		//收集
    		for (int j = 0; j < radix.size(); ++j) {
    			for (auto& r : radix[j]) {
    				nums[index++] = r;
    			}
    		}
    	}
    }

计数排序

  • 先扫描得到待排序数组中的最大值maxVal与最小值minVal，之后分配一个长度为 maxVal-minVal+1 的计数数组，之后扫描待排序元素，将其所在的计数数组的位置加一。最后再扫描一遍计数器数组，按顺序把值收集起来。注：计数排序实际上是桶排序的一种特例，即k=maxVal-minVal+1;
  • 时间复杂度：平均：O(n+k)；最好：O(n+k)；最坏：O(n+k)
    空间复杂度：O(k)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    //计数排序
    void CountSort(vector<int>& nums) {
    	if (nums.size() < 2) return;
    	int maxVal = INT32_MIN;
    	int minVal = INT32_MAX;
    	for (int i = 0; i < nums.size(); ++i) {
    		maxVal = max(maxVal, nums[i]);
    		minVal = min(minVal, nums[i]);
    	}
    	int k = maxVal - minVal + 1;
    	vector<int>count(k);
    	//计数
    	for (int i = 0; i < nums.size(); ++i)
    		++count[nums[i] - minVal];
    	int index = 0;
    	//收集
    	for (int i = 0; i < count.size(); ++i) {
    		while (count[i] > 0) {
    			nums[index++] = i + minVal;
    			--count[i];
    		}
    	}
    }

堆排序

  • 堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个节点的值都小于或等于其左右孩子结点的值，成为小顶堆。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    void maxHeapify(vector<int>& a,int i,int heapSize){
    	int l = i*2 + 1;
    	int r = i*2 + 2;
    	int large = i;
    	if(l < heapSize && a[l] > a[large]){
    		large = l
    	}
    	if(r < heapSize && a[r] > a[large]){
    		large = r;
    	}g
    	if(large != i){
    		swap(a[i], a[large]);
    		maxHeapify(a, large, heapSize);
    	}
    }
    void buildMaxHeap(vector<int>& a,int heapSize){
    	for(int i = heapSize/2;i >= 0;--i){
    		maxHeapify(a,i,heapSize);
    	}
    }
    参考文献