常用排序算法总结
插入排序
- 一般方法 ：
在第P趟，将位置P上的元素向左移动到它在前P+1个元素中的正确位置上。对于P=1到P=N-1趟，插入排序保证从位置0到位置P上的元素为已排序状态。
- 复杂度
最好的情况：数组完全有序，每次插入只需要和插入位置的前一个元素，因此复杂度为O(N);
最坏的情况：数组完全逆序，在插入第n个位置时，需要比较前n-1 个，次数为1+2+···+n-1+n=n*(n-1)/2. 因此复杂度为O(n^2).
JavaScript算法实现
function InsertionSort(arr,n) {
var j,p,temp;//p趟插入,n=arr.length时能完全排序
for (p = 1; p < n; p++) {
temp = arr[p];
for(j=p; j>0&&arr[j-1]>temp; j--) {
arr[j] = arr[j-1];
}
arr[j] = temp;
}
return arr;
}
快速排序
- 算法步骤
- 如果数组S的元素个数是1或0，则返回。
- 取S中任一元素v，作为枢纽 元。
- 将S-{v} 分为两个不相交的集合：S1={x∊S-{v} | x<=v} 和 S2={x∊S-{v} | x>=v}
- 返回 { quicksort(s1)后，继而v,进而 quicksort(s2) }
- 算法分析
它的平均运行时间为O(N log N),它的最坏性能为O(N^2).
- 算法思想以及算法实现
- 选取枢纽元
三中值法：一般方法是选择左端、右端和中心位置上的三个元素中值作为枢纽元
var media3 = arr[0].concat(pivot,arr.pop()).sort((a,b)=>{return a-b;})[1];
后面用递归法实现s1 . s2 的排序
function quickSort(arr) {
if(arr.length<=1){
return arr;
}
var pivotIndex = parseInt(arr.length/2);
var pivot = arr.splice(pivotIndex,1)[0];//直接选取中间值为枢纽元
var left = [];
var right = [];
for(var i=0;i<arr.length;i++) {
if(arr[i]<pivot){
left.push(arr[i]);
}
else{
right.push(arr[i]);
}
}
return quickSort(left).concat(pivot,quickSort(right));
}
