0.公共方法
function swap(arr,a,b){
var tmp=arr[b];
arr[b]=arr[a];
arr[a]=tmp;
}
function generateRandomArray(n, rangeL, rangeR) {
var arr = [];
for (var i = 0; i < n; i++) {
arr.push(Math.floor(Math.random() * (rangeR - rangeL + 1))+ rangeL)
}
return arr;
}
function generateNearlyOrderedArray(n,swapTimes){
var arr=[];
for(var i=0;i<n;i++){
arr[i]=i;
}
for(var i=0;i<swapTimes;i++){
var posx=Math.floor(Math.random()*n)
var posy=Math.floor(Math.random()*n)
swap(arr,posx,posy)
}
return arr;
}
function testSort(sortName, fn,arr,n) {
var start = Date.now();
console.log(start)
fn(arr,n);
var end = Date.now();
console.log(end);
var time = (end - start)/1000;
if(!isSorted(arr,n))
{
console.log("数组还未排序成功！")
return false;
}
console.log(sortName+": "+time+"秒");
}
function isSorted(arr, n) {
for (var i = 0; i < n - 1; i++) {
if (arr[i + 1] < arr[i])
return false;
return true;
}
}
function copyArray(arr){
return arr.map(function(item){
return item;
})
}
1. 选择排序
function selectionSort(arr,n){
for(var i=0;i<n;i++){
var minIndex=i;
for(var j=i+1;j<n;j++){
if(arr[j]<arr[minIndex])
minIndex=j
}
swap(arr,minIndex,i)
}
}
var arrTest=[9,6,13,4,10,8,12]
selectionSort(arrTest,arrTest.length)
console.log(arrTest)
2. 插入排序
function insertionSort(arr, n) {
if (arguments.length == 3) {
var l=arguments[1];
var r=arguments[2]
for (var i = l + 1; i <= r; i++) {
var e = arr[i];
var j = null
for (j = i; j > 0 && arr[j - 1] > e; j--) {
arr[j] = arr[j - 1]
}
arr[j] = e
}
}
else {
for (var i = 1; i < n; i++) {
var e = arr[i];
var j = null
for (j = i; j > 0 && arr[j - 1] > e; j--) {
arr[j] = arr[j - 1]
}
arr[j] = e
}
}
}
3. 归并排序
function mergeSort(arr, n) {
__mergeSort(arr, 0, n - 1);
}
// 递归使用归并排序,对arr[l...r]的范围进行排序
function __mergeSort(arr, l, r) {
/* if( l >= r )
return; */
if (r - l <= 15) {
insertionSort(arr, l, r);
return;
}
var mid = Math.floor((l + r) / 2);
__mergeSort(arr, l, mid);
__mergeSort(arr, mid + 1, r);
if (arr[mid] > arr[mid + 1])
__merge(arr, l, mid, r);
}
// 将arr[l...mid]和arr[mid+1...r]两部分进行归并
function __merge(arr, l, mid, r) {
var aux = [];
for (var i = l; i <= r; i++)
aux[i - l] = arr[i];
// 初始化，i指向左半部分的起始索引位置l；j指向右半部分起始索引位置mid+1
var i = l, j = mid + 1;
for (var k = l; k <= r; k++) {
if (i > mid) { // 如果左半部分元素已经全部处理完毕
arr[k] = aux[j - l]; j++;
}
else if (j > r) { // 如果右半部分元素已经全部处理完毕
arr[k] = aux[i - l]; i++;
}
else if (aux[i - l] < aux[j - l]) { // 左半部分所指元素 < 右半部分所指元素
arr[k] = aux[i - l]; i++;
}
else { // 左半部分所指元素 >= 右半部分所指元素
arr[k] = aux[j - l]; j++;
}
}
}
4.1 原始版快速排序
// 对arr[l...r]部分进行partition操作
// 返回p, 使得arr[l...p-1] < arr[p] ; arr[p+1...r] > arr[p]
function __partition(arr, l, r){
var v = arr[l];
var j = l; // arr[l+1...j] < v ; arr[j+1...i) > v
for( var i = l + 1 ; i <= r ; i ++ )
if( arr[i] < v ){
j ++;
swap( arr ,j ,i );
}
swap( arr , l , j);
return j;
}
// 对arr[l...r]部分进行快速排序
function __quickSort( arr, l, r){
if( l >= r )
return;
var p = __partition(arr, l, r);
__quickSort(arr, l, p-1 );
__quickSort(arr, p+1, r);
}
function quickSort( arr, n){
__quickSort(arr, 0, n-1);
}
4.2 随机化取值快速排序
function _partition( arr, l, r){
// 随机在arr[l...r]的范围中, 选择一个数值作为标定点pivot
swap( arr,l , Math.ceil(Math.random(r-l+1))+l );
var v = arr[l];
var j = l;
for( var i = l + 1 ; i <= r ; i ++ )
if( arr[i] < v ){
j ++;
swap( arr,j , i );
}
swap( arr,l , j);
return j;
}
// 对arr[l...r]部分进行快速排序
function _quickSort( arr, l, r){
// 对于小规模数组, 使用插入排序进行优化
if( r - l <= 15 ){
insertionSort(arr,l,r);
return;
}
var p = _partition(arr, l, r);
_quickSort(arr, l, p-1 );
_quickSort(arr, p+1, r);
}
function quickSort( arr, n){
_quickSort(arr, 0, n-1);
}
4.3 双路快速排序
// 双路快速排序的partition
// 返回p, 使得arr[l...p-1] < arr[p] ; arr[p+1...r] > arr[p]
function _partition2( arr, l, r){
// 随机在arr[l...r]的范围中, 选择一个数值作为标定点pivot
swap(arr,l, Math.ceil(Math.random(r - l + 1)) + l);
var v = arr[l];
// arr[l+1...i) <= v; arr(j...r] >= v
var i = l + 1, j = r;
while (true) {
// 注意这里的边界, arr[i] < v, 不能是arr[i] <= v
// 思考一下为什么?
while (i <= r && arr[i] < v)
i++;
// 注意这里的边界, arr[j] > v, 不能是arr[j] >= v
// 思考一下为什么?
while (j >= l + 1 && arr[j] > v)
j--;
// 对于上面的两个边界的设定, 有的同学在课程的问答区有很好的回答:)
// 大家可以参考: http://coding.imooc.com/learn/questiondetail/4920.html
if (i > j)
break;
swap(arr,i,j);
i++;
j--;
}
swap(arr,l, j);
return j;
}
function _quickSort( arr, l, r){
// 对于小规模数组, 使用插入排序进行优化
if (r - l <= 15) {
insertionSort(arr, l, r);
return;
}
// 调用双路快速排序的partition
var p = _partition2(arr, l, r);
_quickSort(arr, l, p - 1);
_quickSort(arr, p + 1, r);
}
function quickSort( arr, n){
_quickSort(arr, 0, n - 1);
}
4.4递归的三路快速排序算法
// 递归的三路快速排序算法
function __quickSort3Ways( arr, l, r){
// 对于小规模数组, 使用插入排序进行优化
if (r - l <= 15) {
insertionSort(arr, l, r);
return;
}
// 随机在arr[l...r]的范围中, 选择一个数值作为标定点pivot
swap(arr,l, Math.ceil(Math.random() * (r - l + 1)) + l);
var v = arr[l];
var lt = l; // arr[l+1...lt] < v
var gt = r + 1; // arr[gt...r] > v
var i = l + 1; // arr[lt+1...i) == v
while (i < gt) {
if (arr[i] < v) {
swap(arr,i, lt + 1);
i++;
lt++;
}
else if (arr[i] > v) {
swap(arr,i, gt - 1);
gt--;
}
else { // arr[i] == v
i++;
}
}
swap(arr,l, lt);
__quickSort3Ways(arr, l, lt - 1);
__quickSort3Ways(arr, gt, r);
}
function quickSort3Ways( arr, n){
__quickSort3Ways(arr, 0, n - 1);
}
// 比较Merge Sort和双路快速排序和三路快排三种排序算法的性能效率
// 对于包含有大量重复数据的数组, 三路快排有巨大的优势
// 对于一般性的随机数组和近乎有序的数组, 三路快排的效率虽然不是最优的, 但是是在非常可以接受的范围里
// 因此, 在一些语言中, 三路快排是默认的语言库函数中使用的排序算法。比如Java:)
5 原地堆排序
function heapSort(arr){
function __shiftDown(arr,n,k){
while(2*k+1<n){
let j=2*k+1;
if(j+1<n&& arr[j+1]> arr[j])
j+=1;
if(arr[k]>= arr[j])
break;
swap(arr,k,j)
k=j
}
}
for(let i=Math.floor(arr.length-1/2);i>=0;i--)
__shiftDown(arr,arr.length,i)
for(let i=arr.length-1;i>0;i--){
swap(arr,0,i)
__shiftDown(arr,i,0)
}
}
网友评论