排序算法（冒泡、快排）

前言

依据不同的原则，排序可以分为五类
- 插入排序
- 交换排序
- 选择排序
- 归并排序
- 基数排序
排序通常有两种基本操作：
- 比较两个关键字的大小；（必要的）
- 将记录从一个位置记录转移到另一个位置；
交换排序
- 冒泡排序
- 快速排序（快排）

冒泡排序（bubble sort）

冒泡排序的基本思想：有N个数，比较相邻两个数，如果前者大于后者，就把两个数交换位置；这样一来，第一趟就可以选出一个最大的数放在最后面；那么经过N-1轮，就完成了所有数的排序。
伪代码

JavaScript实现


function bubbleSort(arr) {
	let swapped = false;// 循环标记，为false时表示整个排序完成
	let len = arr.length;// 数的个数，也是数组的长度
	let temp;// 临时变量
	do {
		
		swapped = false;
		
		for(let i = 0; i < len - 1; i++) {
			if(arr[i] > arr[i + 1]) {
				
				// 左右比较数交换位置
				 temp=arr[i];
		                 arr[i]=arr[i+1];
		                 arr[i+1]=temp;
		                 swapped = true;
				
			}
		}
		len --; 
		// 递减表示，每一轮比较之后，都会把最大的数排在数组的末尾，
		// 所以不需要再比较这个很大的数，因此比较数的个数需要递减
	} while(swapped);
	return arr;
}

快排（quick sort）

快排是对冒泡排序的一种改进，其基本思想是：对N个数进行一趟排序能达到将数据分割成两部分，一部分的所有数据都比另一部分的所有数据都要小。然后再按此方法，对这两部分数据进行相同的处理，直到完成排序。
快速排序算法非常适用于大型数据集合；在处理小数据集时性能反而会下降。快速排序是处理大数据集最快的排序算法之一。它是一种分而治之的算法，通过递归的方式将数据依次分解为包含较小元素和较大元素的不同子序列。
代码一（实现普遍、易懂，Java版本也是这样实现)

function partition(arr, low, high) {
	let key = arr[low]; // 关键字
	while(low < high) {
		
		while(low < high && key <= arr[high]) {
			high--;
		}
		arr[low] = arr[high];
		while(low < high && key >= arr[low]) {
			low++;
		} 
		arr[high] = arr[low];
	}
	arr[low] = key;
	return low;
}
function quickSort(arr, low, high) {
	if(low < high || arr != null) {
		let p = partition(arr, low, high);
		quickSort(arr, low, p - 1);
		quickSort(arr, p + 1, high);
	}
	return arr;
}

代码二（实现更加简洁）

Array.prototype.sort

JavaScript原生数组对象的sort，是优化过的快排算法。
不过，此方法需要接收一个比较函数为参数。
代码


// 比较函数
function compare(num1, num2) {
	// 需要根据返回的结果来看
	// 返回负数，num1排在num2前
	// 返回0，num1与num2位置不变
	// 返回正数，num1排在num2后
	
	return num1 - num2; // 升序
	// return num2 - num1; // 降序
}
let arr = [1, 2, 3];
arr.sort(compare);
console.log(arr);