排序算法总结

文章目录

二路归并排序
- 简介
- 算法实现
- - Java
- 参考
快速排序
- 简介
- 算法分析
- 基准元素的选取
- 算法特性
- 算法实现
- - 单边循环法
  - - Java
  - 双边循环法
  - - C++
    - Java
  - 非递归方式
  - - Java
- Q&A
- 参考

二路归并排序简介

二路归并排序是经典的排序算法，核心思想是分治，属于稳定排序
二路归并的递归路径实质上是一个完全二叉树，每次合并操作的平均时间复杂度为O(n)，而完全二叉树的深度为log2n。因此总的平均时间复杂度为O(nlogn)
而且，归并排序的最好，最坏，平均时间复杂度均为O(nlogn)
当然还有n路归并排序

算法实现 Java

public class MergeSort {
    public static void main(String[] args) {
        int[] a = {1,4,2,8,3,7,8,4,6,9};
        System.out.println(Arrays.toString(a));
        int[] temp = new int[a.length];//在外部声明辅助数组，避免在递归栈中声明
        mergeSort(a, 0, a.length - 1, temp);

        System.out.println(Arrays.toString(a));
    }
    public static void mergeSort(int[] arr, int left, int right, int[] temp){
        if (left >= right) return;
        int mid = (left + right) >> 1;
        mergeSort(arr, left, mid, temp);
        mergeSort(arr, mid+1, right, temp);
        int l = left, r = mid + 1;
        int t = 0;//辅助计数变量
        while (l <= mid && r <= right){
            if (arr[l] < arr[r]) temp[t++] = arr[l++];
            else temp[t++] = arr[r++];
        }
        //剩下的子序列添加到辅助空间中
        while (l <= mid) temp[t++] = arr[l++];
        while (r <= right) temp[t++] = arr[r++];
        //将辅助数组的值copy到原数组,注意copy到原数组的范围是left到right
        t = 0;
        while (left <= right) arr[left++] = temp[t++];
    }
}

参考

https://www.cnblogs.com/chengxiao/p/6194356.html

快速排序简介

快排与傅里叶变换等算法并称为二十世纪十大算法
使用了分治法
冒泡排序在每一轮只把一个元素冒泡到数列的一端，而快速排序在每一轮挑选一个基准元素，并让其他比它大的元素移动到数列一边，比它小的元素移动到数列的另一边，从而把数列拆解成了两个部分。在分治法的思想下，原数列在每一轮被拆分成两部分，每一部分在下一轮又分别被拆分成两部分，直到不可再分为止。

算法分析

这样一共需要多少轮呢？

最好情况：每次划分都产生两个长度差不多的子区间，也就是说，所取得基准都是当前无序区的中值元素，这样的递归树的高度为：

l o g 2 n log_2 n log2n

而每一层划分的时间为n，所以：

T n = O ( n l o g n ) ， S ( n ) = O ( l o g 2 n ) （递归栈空间） Tn = O(nlogn)，S(n) = O(log_2n)（递归栈空间） Tn=O(nlogn)，S(n)=O(log2n)（递归栈空间）

最坏情况：每次选取得基准都是当前无序区的最大（小）值，这样的话，递归树高度n，需要n-1次划分：

T n = O ( n 2 ) ， S ( n ) = O ( n ) Tn = O(n^2) ， S(n) = O(n) Tn=O(n2)，S(n)=O(n)

平均情况：

T n = O （ n l o g n ） Tn = O（nlogn） Tn=O（nlogn）

基准元素的选取

基准元素，英文pivot。
最简单的方式是选择数列的第一个元素，这种选择在绝大多数情况是没有问题的。但是，假如有一个原本逆序的数列，期望排序成顺序数列，那么会出现什么情况呢？时间复杂度退化为：

n 2 n^2 n2

当然，即使是随机选择基准元素，每一次也有极小的几率选到数列的最大值或最小值，同样会影响到分治的效果

算法特性

不稳定
原地排序

算法实现单边循环法 Java

仅仅需要修改双边循环法的partition函数

public static int partition2(int[] arr, int front, int back){
    int pivot = front;
    int mark = front;//代表小于基准元素的区域边界
    for (int i = front+1; i <= back; i++){
        if (arr[i] < arr[pivot]){
            mark++;//因为找到一个小于基准元素的元素
            swap(arr, i, mark);
        }
    }
    swap(arr, pivot, mark);
    return mark;
}

双边循环法

这种方法虽然理解起来差不多，但代码实现要复杂一点，容易出错，个人还是更喜欢单边循环法，代码更简洁

C++

#include
using namespace std;

void disppart(int *a, int f, int b){
	
	static int i = 1;
	cout << "第" << i << "次划分：" << endl;
	for(int j = 0; j < f; j++)
		cout << "  ";
	for(int j = f; j <= b; j++)
		cout << a[j] << " ";
	cout << endl; 
	i++;
}

int partition(int *a, int f, int b){
	int pivot = f;//pivot = a[f]
	int front = f, back = b;
	int temp = 0;
	while(1){	
		while(front < back && a[back]  >= a[pivot]) back--;//这两个while的顺序看似无关紧要，实际上是很关键的
		while(front < back && a[front] <= a[pivot]) front++;
        if(front < back){
			temp = a[front];
			a[front] = a[back];
			a[back] = temp;
		}	
		else 
			break;	
	}
	temp = a[pivot];
	a[pivot] = a[front];
	a[front] = temp;
	disppart(a, f, b);
	return back;	//return front 也行
}
void QuickSort(int *a, int f, int b){
	int mid = 0;	
	if(f < b){
		mid = partition(a, f, b);
		QuickSort(a, f, mid - 1);
		QuickSort(a, mid + 1, b);
	}
}

int main(){
	int a[10] = {6,8,7,9,0,1,3,2,4,5};
	QuickSort(a, 0, 9);
	for(int i = 0; i < 10; i++)
		cout << a[i] << " ";
	return 0;
}

Java

import java.util.Arrays;

public class QuickSort {
	public static void main(String[] args) {
		int[] arr = {6,8,7,9,0,1,3,2,4,5};
//		System.out.println(Arrays.toString(arr));
		sort(arr, 0, 9);
		System.out.println(Arrays.toString(arr));
	}
	public static void sort(int[] arr, int front, int back) {
		int mid = 0;
		if(front < back) {
			mid = partition(arr, front, back);
			sort(arr, front, mid-1);
			sort(arr, mid+1, back);
		}
	}
	public static int partition(int[] arr, int front, int back) {
		int pivot = front;
		int f = front, b = back;
		while(true) {
			while(f < b && arr[b] >= arr[pivot]) b--;
			while(f < b && arr[f] <= arr[pivot]) f++;
			if(f < b) swap(arr, f, b);
			else break;
		}
		swap(arr, pivot, f);
		return f;
	}
	public static void swap(int[] arr, int front, int back) {
		int temp = arr[front];
		arr[front] = arr[back];
		arr[back] = temp;
	}
}

非递归方式

和递归实现相比，非递归方式代码的变动只发生在quickSort方法中。该方法引入了一个存储Map类型元素的栈，用于存储每一次交换时的起始下标和结束下标。
每一次循环，都会让栈顶元素出栈，通过partition方法进行分治，并且按照基准元素的位置分成左右两部分，左右两部分再分别入栈。当栈为空时，说明排序已经完毕，退出循环

Java

public static void quickSort2(int[] arr, int startIndex, int endIndex) {
    // 用一个集合栈来代替递归的函数栈
    Stack> quickSortStack = new Stack<>();
    // 整个数列的起止下标，以哈希的形式入栈
    Map rootParam = new HashMap<>();
    rootParam.put("startIndex", startIndex);
    rootParam.put("endIndex", endIndex);
    quickSortStack.push(rootParam);

    // 循环结束条件：栈为空时
    while (!quickSortStack.isEmpty()) {
        //  栈顶元素出栈，得到起止下标
        Map param = quickSortStack.pop();
        //  得到基准元素位置
        int pivotIndex = partition(arr, param.get("startIndex"), param.get("endIndex"));
        //  根据基准元素分成两部分, 把每一部分的起止下标入栈
        if (param.get("startIndex") < pivotIndex - 1) {
            Map leftParam = new HashMap<>();
            leftParam.put("startIndex", param.get("startIndex"));
            leftParam.put("endIndex", pivotIndex - 1);
            quickSortStack.push(leftParam);
        }
        if (pivotIndex + 1 < param.get("endIndex")) {
            Map rightParam = new HashMap<>();
            rightParam.put("startIndex", pivotIndex + 1);
            rightParam.put("endIndex", param.get("endIndex"));
            quickSortStack.push(rightParam);
        }
    }
}

Q&A

Q: 注意双边循环法Java实现第22、23行，为什么要先让back - - ？

因为此题的设定是从小到大（从左到右）排序，在最后的时候（即front==back），必须让他们所指的元素小于pivot元素（因为每次partition的最后还有一次swap），那么就必须先让back先–，因为back寻找的是就是小于pivot的元素，如果先让front++，它在最后时刻找到的就是大于pivot的元素，这就可能error了

Q: 那么如果是从大到小（从左到右）排序呢？（以第一个元素为pivot）

这个时候，显然back这时候就该寻找最大的了，所以还是该让back先ki走，到最后时刻才不会找到最小的。这种情况只需修改22、23行里的判断条件就可以了。

Q: 当然，那么还有一个问题，如果以最后一个元素为pivot呢？

答案是：这时候就让front先走

总结：所以只存在两种情况：取决于pivot的位置。

如果在最前，就让back先走；在最后，就让front先走（无论从小到大还是从大到小）
一般取pivot在前，然后排序顺序不同的话只需要修改22、23行就行了

参考

《漫画算法》by 程序员小灰

排序算法 总结

Java相关栏目本月热门文章

排序算法总结