排序算法学习笔记
排序算法
稳定性：如果a原本在b前面且a=b,排序之后a仍然在b前面，则稳定；如果排序之后a可能会在b后，则不稳定。
非线性时间比较类排序
通过比较来决定元素间的相对次序，时间复杂度不能突破O(nlogn)。
交换排序
冒泡排序(bubble sort)
一次比较两个元素，如果顺序不对则交换过来。
时间复杂度：O(n^2),优化后最好时间复杂度可为O(n)。
空间复杂度：O(1)。
稳定性：稳定。
示例代码：
//普通
function srotfunction($a){
$count = count($a);
for($i=$count-1; $i>0; $i--){
for($j=0;$j<$i;$j++){
if($a[$j] > $a[$j+1]){
$tmp = $a[$j];
$a[$j] = $a[$j+1];
$a[$j+1] = $tmp;
}
}
}
return $a;
}
//优化后，用 didswap 标记是否有交换动作。如果本身有序，则执行一次。
function srotfunction($a){
boolean $didswap;
$count = count($a);
for($i=$count-1; $i>0; $i--){
$didswap = false;
for($j=0;$j<$i;$j++){
if($a[$j] > $a[$j+1]){
$tmp = $a[$j];
$a[$j] = $a[$j+1];
$a[$j+1] = $tmp;
$didswap = true;
}
}
if($didswap == false){
break;
}
}
return $a;
}快速排序(quick sort)
通过基准元素，分为两组子串，继续对字段分组，以达到整个序列有序。基准元素一般选择第一个元素或最后一个元素。
时间复杂度：O(nlogn)。
空间复杂度：O(nlogn)。
稳定性：不稳定。
代码示例：
function partition(&$a, $low, $high){
$privotKey = $a[$low];
while($low<$high){
//大于的部分
while($low<$high && $a[$high]>$privotKey){
--$high;
}
swap($a, $low, $high);
while($low<$high && $a[$low]<$privotKey){
++$low;
}
swap($a, $low, $high);
}
return $low;
}
function quicksort(&$a, $low, $high){
if($low < $high){
$privotloc = partition($a, $low, $high);
quicksort($a, $low, $privotloc-1);
quicksort($a, $privotloc+1, $high);
}
}
$b = quicksort($a, 0, count($a)-1);插入排序
简单插入排序(insertion sort)
构建有序序列，对未排序单元，在已排序序列中从后向前扫描，找到相应位置并插入。
时间复杂度：O(n^2),已有序只比较一次，复杂度为O(n)。
空间复杂度：O(1)。
稳定性：稳定。
代码示例：
function srotfunction($a){
$len = count($a);
for($i=1; $i<$len; $i++){
$current = $a[$i];
$preIndex = $i - 1;
while($preIndex >=0 && $a[$preIndex] > $current){
$a[$preIndex+1] = $a[$preIndex];
$preIndex--;
}
$a[$preIndex + 1] = $current;
}
return $a;
}希尔排序(shell sort)
把数据按下标增量分为多个分组，每组内用插入排序。希尔增量序列{n/2, (n/2)/2, ..., 1}。
时间复杂度：O(n^2)。一些优化的增量序列可以为O(n^3/2)。已经有序的为O(n)。
空间复杂度：O(1)。
稳定性：不稳定。
代码示例：
function srotfunction($a){
$len = count($a);
$gap = intval($len / 2);
for(;$gap>0;$gap=intval($gap/2)){
for($i=$gap;$i<$len;$i++){
$j = $i;
$tmp = $a[$i];
if($a[$j] < $a[$j-$gap]){
while($j-$gap>=0 && $a[$j-$gap]>$tmp){
$a[$j] = $a[$j-$gap];
$j-=$gap;
}
$a[$j] = $tmp;
}
}
}
return $a;
}选择排序
简单选择排序(selection sort)
从未排序字段中找到最小（最大）的元素，放入已排序字段中。
时间复杂度：O(n^2)。
空间复杂度：O(1)。
代码示例：
function srotfunction($a){
$len = count($a);
for($i=0; $i<$len-1; $i++){
$min = $i;
for($j=$i+1; $j<$len; $j++){
if( $a[$min] > $a[$j]){
$min = $j;
}
}
if($min != $i){
$tmp = $a[$min];
$a[$min] = $a[$i];
$a[$i] = $tmp;
}
}
return $a;
}堆排序(heap sort)
利用堆的数据结构，反复调整结构以使其满足堆定义。
堆：完全二叉树，每个节点的值都大于或等于其左右孩子节点的值（大顶堆），同理小顶堆。
时间复杂度：O(nlogn)。
空间复杂度：O(1)。
基本思路：
- 将无序序列构造为一个堆（大顶堆-升序，小顶堆-降序）；
- 将堆顶元素与末尾元素交换，使最大（最小）元素到数组末尾；
- 重新调整结构，使其满足堆定义;
- 继续交换堆顶元素与当前末尾元素，反复调整交换，使序列有序。
归并排序(merge sort)
分治法，将已有有序子序列合并获得有序序列。二路归并排序、多路归并排序。
时间复杂度：O(nlogn)。
空间复杂度：O(n)。
稳定性：稳定。
代码示例：
function mergeSort(arr) { // 采用自上而下的递归方法
var len = arr.length;
if (len < 2) {
return arr;
}
var middle = Math.floor(len / 2),
left = arr.slice(0, middle),
right = arr.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right) {
var result = [];
while (left.length>0 && right.length>0) {
if (left[0] <= right[0]) {
result.push(left.shift());
} else {
result.push(right.shift());
}
}
while (left.length)
result.push(left.shift());
while (right.length)
result.push(right.shift());
return result;
}线性时间非比较类排序
不通过比较来决定次序，可以以线性时间运行。
计数排序(counting sort)
将输入的数据值转化为键，存储在额外的数组空间中。要求输入的数据必须是有确定范围的整数，k不是很大且序列比较集中时。
时间复杂度：O(n+k) //输入元素是n个0~k之间的整数
空间复杂度：O(n+k)
稳定性：稳定
算法描述：
- 找到数组中最大、最小的值，构建新数组c[min, max];
- 统计数组中值为i的元素，放入c[i],并累加次数;
- 统计完后，将c中元素根据i和值放入新数组。
桶排序(bucket sort)
利用函数的映射关系，计数排序的升级版。
算法描述：
- 假设数据服从均匀分布，将数据分到有限数量的桶里；
- 对每个桶分别排序（使用其他排序算法或者桶排序）；
- 将非空桶数据拼接起来。
基数排序(radix sort)
先按低位优先级排序、收集，再按高位优先级排序、收集，以此类推。
算法复杂度图表
