We read every piece of feedback, and take your input very seriously.
To see all available qualifiers, see our documentation.
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
2019年03月16日
稳定性：如果待排序的序列中存在值相等的元素，经过排序后，相等元素之间原有的先后顺序不变，我们就说这种排序算法是稳定的排序算法。
原地排序：是针对空间复杂度引入的一个概念，它特指指空间复杂度为O(1)的排序算法。
为了下面时间复杂度分析方便，我们先介绍下"有序度"和"逆序度"。 有序度是数组中具有有序关系的元素对的个数，逆序度是数组中具有逆序关系的元素对的个数：
有序元素对：a[i] <= a[j] ，如果 i<j 逆序元素对：a[i] > a[j]，如果i<j
有序元素对：a[i] <= a[j] ，如果 i<j
逆序元素对：a[i] > a[j]，如果i<j
比如[2，4，3，1，5，6]这组数组，其有序元素对有： (2,4)、(2,3)、(2,5)、(2,6)、(4,5)、(4,6)、(3,5)、(3,6)、(1,5)、(1,6)、(5,6) 共11个，所以其有序度为11；
其逆序元素对有： (2,1)、(4,3)、(4,1)、(3,1) 共4个，所以其逆序度为4。
比如[6，5，4，3，2，1]的有序度是0；
而对于[1，2，3，…，n]这样完全有序的数组，其有序度就是 $$ C_n^2 = \frac{n(n-1)}{2} $$ 我们把这种完全有序的数组有序度叫做满有序度。
比如[1，2，3，4，5，6]的满有序度为15。
有序度 + 逆序度 = 满有序度。我们排序的过程就是一种增加有序度、减少逆序度的过程，最后达到满有序度、就说明排序完成了。 对数组进行交换以使其逐渐有序，假设每交换一次有序度就加1，那么不管算法如何改进、交换次数总是确定的，即为逆序数。
下面的排序算法都实现升序排序。
优化：当某次冒泡已经没有数据交换了，说明已经达到有序了，也就可以不再执行后续冒泡。
代码：
// 冒泡排序 function bubbleSort (array) { if (!array || array.length <= 1) { return; } let len = array.length; for (let i=0; i<len; i++) { let flag = false; // 本轮冒泡是否有数据交换 for (let j=0; j<len-i-1; j++) { if (array[j]>array[j+1]) { let temp = array[j+1]; array[j+1] = array[j]; array[j] = temp; flag = true; } } if (!flag) { break; // 本轮冒泡没有数据交换，提前退出 } } }
由代码可以看出：
插入排序顾名思义，通过将元素插入数组中它该在的位置来进行排序。
// 插入排序 function insertSort (array) { if (!array || array.length <= 1) { return; } let len = array.length; // 遍历未排序区 for (let i = 1; i<len; i++) { let val = array[i]; let j = i-1; // 在已排序区查找插入位置 for (; j>=0; j--) { if (array[j] > val) { // 比较 array[j+1] = array[j]; // 移动 } else { break; } } array[j+1] = val; // 找到插入位置、插入[1.已排序区未遍历完找到插入位置，break;出来插入；2.以排序区已遍历完、已排序区所有元素右移一位、所以在遍历结束后插入到已排序前第1位] } }
另外，冒泡排序和插入排序不管怎么优化，它们的元素交换/移动（插入排序的移动也是增加有序度的过程）次数是固定的、为逆序度，但是从代码上看，冒泡排序的数据交换要比插入排序的数据移动复杂，冒泡需要3个赋值操作，而插入只需1个移动操作：
// 冒泡排序中数据的交换操作 if (array[j]>array[j+1]) { let temp = array[j+1]; array[j+1] = array[j]; array[j] = temp; flag = true; } // 插入排序中数据的移动操作 if (array[j] > val) { // 比较 array[j+1] = array[j]; // 移动 } else { break; }
所以虽然都是O(n^2)时间复杂度，如果我们希望把性能优化做的极致，比起冒泡排序、肯定选插入排序（插入排序还有很大优化空间，比如希尔排序）。
插入排序每次都需要在已排序区遍历查找插入位置，如果我们只在已排序区末尾插入呢？那就是选择排序。(插入排序重点在插入；而选择排序，顾名思义，重点在选择。)
// 选择排序 function selectSort(array) { if(!array || array.length<=1) { return; } let len = array.length; for(let i=0; i<len-1; i++) { let min = i; for (let j=i+1; j<len; j++) { if (array[j] < array[min]) { min = j; // 找到未排序区中的最小元素 } } // 将未排序区中的最小元素通过交换方式放入已排序区末尾 let temp = array[i]; array[i] = array[min]; array[min] = temp; } }
// 归并排序 function mergeSort(array) { if (!array || array.length<=1) { return; } sort(array, 0, array.length-1); } function sort (array, left, right) { if (left > right) { return; } let mid = Math.floor((left + right)/2); merge(sort(array, left, mid), sort(array, mid+1, right)) } function merge (array1, array2) { let len1 = array1.length, len2 = array2.length; let result = new Array(len1+len2); let i = j = 0; while (i<=len1 && j<=len2) { if (array1[i] <= array[j]) { result.push(array1[i]); i++; } else { result.push(array2[j]); j++; } } while (i<=len1) { result.push(array1[i]); i++; } while (j<=len2) { result.push(array2[j]); j++; } return result; }
归并排序稳不稳定要看merge()函数，代码中当左右数组存在相同值时、先把左数组的值放入合并的数组，这样保证了稳定性，所以归并排序是一个稳定的排序算法；
归并排序时间复杂度 = 子问题时间复杂度 * 2 + 合并的时间复杂度 根据上面代码递推公式我们可以得到时间复杂度递推公式：
T1 = C; n=1时只需要常量级的执行时间 Tn = 2 * T(n/2) + n; n >1
所以：
Tn = 2 * T(n/2) + n = 2 * (2 * T(n/4) + n/2) + n = 4 * T(n/4) + 2n = 2 * (2 * (2 * T(n/8) + n/4) + n/2) + n = 8 * T(n/8) + 3n = ... = 2^k * T(n/2^k) + k * n = ...
当T(n/2^k) = T(1)时 => n/2^k = 1 => 2^k = n => k = log2(n)。
根据递归终止条件：T1 = C，Tn = n * C + n * log2(n)。
所以用大O表示法，Tn就等于O(nlogn)，即归并排序的时间复杂度是O(nlogn)。
我们从原理和代码可以看出，归并排序的执行效率与要排序的原始数组的有序程序无关，所以其最好、最坏、平均情况时间复杂度都是O(nlogn)。
但是归并排序有一个致命弱点，那就是它不是原地排序的，它的空间复杂度是O(n)。[尽管每次合并都需要申请额外空间，但是在合并操作结束后，临时开辟的控件就被释放掉了，所以临时空间最多也就是n。]
// 快速排序 function quickSort (array) { if (!array || array.length<=1) { return; } sort(array, 0, array.length-1); } function sort(array, left, right) { // 区间缩小至区间内只有1个元素、则该区间已经排好序 if (left >= right) { return; } let pivot = partition(array, left, right); // 获取分区点 sort(array, left, pivot-1); sort(array, pivot+1, right) } function partition (array, left, right) { // 为了实现原地排序算法，采用类似选择排序的 从“未处理区”取出小于pivot的元素插入到“已处理区”末尾，通过交换方式 // 这里选取最后一个元素为pivot let pivot = array[right]; let i = left; // 标记”已处理区“尾部 for (let j=left; j<=right-1; j++) { // 注意：从left到right-1找小于pivot的元素、将其放到左边“已处理区” if (array[j]<pivot) { let temp = array[i]; array[i] = array[j]; array[j] = temp; i++; } } // 将pivot放到中间 let temp = array[i]; array[i] = array[right]; array[right] = temp; // 返回分区点 return i; }
注意：上述代码中"已处理区"并不是真的如插入、选择排序一样的已排好序的区域，而是为了更好理解分区操作中跟选择排序类似的通过交换方式、从“未处理区”取出小于pivot的元素插入到“已处理区”末尾
另外，
桶排序顾名思义，"桶"是用来排序的主角。
计数排序其实是桶排序的一种特殊情况。
另外经典排序还有希尔排序、堆排序等，下次有空再整理把。
The text was updated successfully, but these errors were encountered:
No branches or pull requests
2019年03月16日
经典排序算法
写在前面
稳定性：如果待排序的序列中存在值相等的元素，经过排序后，相等元素之间原有的先后顺序不变，我们就说这种排序算法是稳定的排序算法。
原地排序：是针对空间复杂度引入的一个概念，它特指指空间复杂度为O(1)的排序算法。
为了下面时间复杂度分析方便，我们先介绍下"有序度"和"逆序度"。
有序度是数组中具有有序关系的元素对的个数，逆序度是数组中具有逆序关系的元素对的个数：
比如[2，4，3，1，5，6]这组数组，其有序元素对有：
(2,4)、(2,3)、(2,5)、(2,6)、(4,5)、(4,6)、(3,5)、(3,6)、(1,5)、(1,6)、(5,6) 共11个，所以其有序度为11；
其逆序元素对有：
(2,1)、(4,3)、(4,1)、(3,1) 共4个，所以其逆序度为4。
比如[6，5，4，3，2，1]的有序度是0；
而对于[1，2，3，…，n]这样完全有序的数组，其有序度就是
$$
C_n^2 = \frac{n(n-1)}{2}
$$
我们把这种完全有序的数组有序度叫做满有序度。
比如[1，2，3，4，5，6]的满有序度为15。
有序度 + 逆序度 = 满有序度。我们排序的过程就是一种增加有序度、减少逆序度的过程，最后达到满有序度、就说明排序完成了。
对数组进行交换以使其逐渐有序，假设每交换一次有序度就加1，那么不管算法如何改进、交换次数总是确定的，即为逆序数。
下面的排序算法都实现升序排序。
冒泡排序
优化：当某次冒泡已经没有数据交换了，说明已经达到有序了，也就可以不再执行后续冒泡。
代码：
由代码可以看出：
插入排序
插入排序顾名思义，通过将元素插入数组中它该在的位置来进行排序。
代码：
由代码可以看出：
另外，冒泡排序和插入排序不管怎么优化，它们的元素交换/移动（插入排序的移动也是增加有序度的过程）次数是固定的、为逆序度，但是从代码上看，冒泡排序的数据交换要比插入排序的数据移动复杂，冒泡需要3个赋值操作，而插入只需1个移动操作：
所以虽然都是O(n^2)时间复杂度，如果我们希望把性能优化做的极致，比起冒泡排序、肯定选插入排序（插入排序还有很大优化空间，比如希尔排序）。
选择排序
插入排序每次都需要在已排序区遍历查找插入位置，如果我们只在已排序区末尾插入呢？那就是选择排序。(插入排序重点在插入；而选择排序，顾名思义，重点在选择。)
代码：
由代码可以看出：
归并排序
代码：
由代码可以看出：
归并排序稳不稳定要看merge()函数，代码中当左右数组存在相同值时、先把左数组的值放入合并的数组，这样保证了稳定性，所以归并排序是一个稳定的排序算法；
归并排序时间复杂度 = 子问题时间复杂度 * 2 + 合并的时间复杂度
根据上面代码递推公式我们可以得到时间复杂度递推公式：
所以：
当T(n/2^k) = T(1)时 => n/2^k = 1 => 2^k = n => k = log2(n)。
根据递归终止条件：T1 = C，Tn = n * C + n * log2(n)。
所以用大O表示法，Tn就等于O(nlogn)，即归并排序的时间复杂度是O(nlogn)。
我们从原理和代码可以看出，归并排序的执行效率与要排序的原始数组的有序程序无关，所以其最好、最坏、平均情况时间复杂度都是O(nlogn)。
但是归并排序有一个致命弱点，那就是它不是原地排序的，它的空间复杂度是O(n)。[尽管每次合并都需要申请额外空间，但是在合并操作结束后，临时开辟的控件就被释放掉了，所以临时空间最多也就是n。]
快速排序
代码：
注意：上述代码中"已处理区"并不是真的如插入、选择排序一样的已排好序的区域，而是为了更好理解分区操作中跟选择排序类似的通过交换方式、从“未处理区”取出小于pivot的元素插入到“已处理区”末尾
由代码可以看出：
另外，
可以发现，归并排序排序处理过程是从下到上的、先处理子问题再合并；快排是从上到下的、先分区再处理子问题。
归并是非原地排序算法(它之所以是非原地排序算法，注意是因为合并函数无法在原地执行)；快排通过设计巧妙的原地分区函数，实现原地排序，解决了归并排序占用太多内存的问题。
桶排序
桶排序顾名思义，"桶"是用来排序的主角。
如果有n个数据，我们把他们均匀分发到m个桶内，那么每个桶就有k = n/m个数据，对每个桶里的数据进行快排，则每个桶的排序时间复杂度是O(klogk)，m个桶的排序时间复杂度就是O(m * klogk) = O(nlog(n/m))。当桶的个数m接近要排序的数据个数n时，桶排序时间复杂度就接近O(n)。
计数排序
计数排序其实是桶排序的一种特殊情况。
基数排序
总结
另外经典排序还有希尔排序、堆排序等，下次有空再整理把。
参考
The text was updated successfully, but these errors were encountered: