品一品プログラミング---5
1261 ワード
問題の説明:
配列ベースsortソート関数の実装
手順は次のとおりです.
//泡立ちソートO(n^2)
//クイックソート---メリット:その場でソートO(n*log 2 n)
配列ベースsortソート関数の実装
var sort = function(arr) {
// your code
}
sort([5, 100, 6, 3, -12]) //[-12, 3, 5, 6, 100]
手順は次のとおりです.
//泡立ちソートO(n^2)
var sort = function(arr) {
var len = arr.length
for(var i = 0; i < len-1; i++) {
for(var j = i+1; j < len; j++) {
if(arr[i] > arr[j]) {
var tmp = arr[i]
arr[i] = arr[j]
arr[j] = tmp
}
}
}
return arr
}
//クイックソート---メリット:その場でソートO(n*log 2 n)
var quickSort = function(arr) {
function sort(left,right) {
var high = right;
var pivot = arr[left];
if(right > left){
while(left < right) {
while(left < right && arr[right] > pivot) {
right--;
};
arr[left] = arr[right];
while(left < right && arr[left] < pivot) {
left++;
}
arr[right] = arr[left];
}
arr[left] = pivot;
sort(0, left);
sort(left+1, high);
}
}
sort(0,arr.length-1);
return arr;
}