資訊專欄INFORMATION COLUMN
摘要：快速排序，參考排序算法的完整實現(xiàn)各種排序算法的完整實現(xiàn)如下冒泡排序選擇排序插入排序歸并排序快速排序，參考排序方法驗證冒泡排序選擇排序插入排序歸并排序快速排序源碼地址的數(shù)據(jù)結(jié)構(gòu)與算法三源碼
1 排序和搜索算法 1.1 排序算法 1.1.1 冒泡排序
冒泡排序比較任何兩個相鄰的項,如果第一個比第二個大,則交換它們。元素項向上移動至正確的順序,就好像氣泡升至表面一樣,冒泡排序因此得名。冒泡排序的時間復(fù)雜度為O(n2)。
//冒泡排序
bubbleSort: function() {
var self = this;
function swap(index1, index2) {
var aux = self.array[index2];
self.array[index2] = self.array[index1];
self.array[index1] = aux;
}
var length = this.array.length;
for (var i = 0; i < length; i++) {
for (var j = 0; j < length - 1 - i; j++) {
if (this.array[j] > this.array[j + 1]) {
swap(j, j + 1);
}
}
}
}
1.1.2 選擇排序
選擇排序算法是一種原址比較排序算法。選擇排序大致的思路是找到數(shù)據(jù)結(jié)構(gòu)中的最小值并將其放置在第一位,接著找到第二小的值并將其放在第二位,以此類推。選擇排序的時間復(fù)雜度為O(n2)。
//選擇排序
selectionSort:function(){
var length = this.array.length;
var indexMin;
for(var i = 0; i < length - 1; i++){
indexMin = i;
for(var j = i; j < length; j++){
if (this.array[indexMin] > this.array[j]) {
indexMin = j;
}
}
if (indexMin !== i) {
this.swap(indexMin,i);
}
}
}
1.1.3 插入排序
有一個已經(jīng)有序的數(shù)據(jù)序列，要求在這個已經(jīng)排好的數(shù)據(jù)序列中插入一個數(shù)，但要求插入后此數(shù)據(jù)序列仍然有序，這個時候就要用到一種新的排序方法——插入排序法,插入排序的基本操作就是將一個數(shù)據(jù)插入到已經(jīng)排好序的有序數(shù)據(jù)中，從而得到一個新的、個數(shù)加一的有序數(shù)據(jù)，算法適用于少量數(shù)據(jù)的排序，時間復(fù)雜度為O(n^2)。是穩(wěn)定的排序方法。插入排序的基本思想是：每步將一個待排序的紀(jì)錄，按其關(guān)鍵碼值的大小插入前面已經(jīng)排序的文件中適當(dāng)位置上，直到全部插入完為止。
insertionSort:function(){
var length = this.array.length;
var j;
var temp;
for(var i = 1; i < length; i++){
temp = this.array[i];
j = i;
while(j > 0 && this.array[j - 1] > temp){
this.array[j] = this.array[j - 1];
j--;
}
this.array[j] = temp;
}
}
1.1.4 歸并排序
歸并排序是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide and Conquer）的一個非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為二路歸并。時間復(fù)雜度為O(nlogn)，空間復(fù)雜度為O(n)。
//歸并排序
mergeSort:function(){
function mergeSortRec(array){
var length = array.length;
if (length === 1) {
return array;
}
var mid = Math.floor(length/2);
var left = array.slice(0,mid);
var right = array.slice(mid,length);
return merge(mergeSortRec(left),mergeSortRec(right));
}
function merge(left,right){
var result = [];
var il = 0;
var ir = 0;
while(il < left.length && ir < right.length){
if (left[il] < right[ir]) {
result.push(left[il++]);
}else{
result.push(right[ir++]);
}
}
while(il < left.length){
result.push(left[il++]);
}
while(ir < right.length){
result.push(right[ir++]);
}
return result;
}
this.array = mergeSortRec(this.array);
}
1.1.5 快速排序
通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個排序過程可以遞歸進(jìn)行，以此達(dá)到整個數(shù)據(jù)變成有序序列。時間負(fù)責(zé)度為O(n^2)，并且比其他負(fù)責(zé)度為O(n^2)的排序算法要好。
//快速排序，參考http://www.ruanyifeng.com/blog/2011/04/quicksort_in_javascript.html
quickSort:function(){
function sort(array){
if (array.length <= 1) {
return array;
}
var pivotIndex = Math.floor(array.length/2);
var pivot = array.splice(pivotIndex,1)[0];
var left = [];
var right = [];
for(var i = 0; i < array.length; i++){
if (array[i] < pivot) {
left.push(array[i]);
}else{
right.push(array[i]);
}
}
return sort(left).concat([pivot],sort(right));
}
this.array = sort(this.array);
}
1.2 排序算法的完整實現(xiàn)
各種排序算法的完整實現(xiàn)如下：
function ArrayList() {
this.array = [];
}
ArrayList.prototype = {
constructor: ArrayList,
insert: function(item) {
this.array.push(item);
},
toString: function() {
return this.array.join();
},
swap: function(index1, index2) {
var aux = this.array[index2];
this.array[index2] = this.array[index1];
this.array[index1] = aux;
},
//冒泡排序
bubbleSort: function() {
var length = this.array.length;
for (var i = 0; i < length; i++) {
for (var j = 0; j < length - 1 - i; j++) {
if (this.array[j] > this.array[j + 1]) {
this.swap(j, j + 1);
}
}
}
},
//選擇排序
selectionSort: function() {
var length = this.array.length;
var indexMin;
for (var i = 0; i < length - 1; i++) {
indexMin = i;
for (var j = i; j < length; j++) {
if (this.array[indexMin] > this.array[j]) {
indexMin = j;
}
}
if (indexMin !== i) {
this.swap(indexMin, i);
}
}
},
//插入排序
insertionSort: function() {
var length = this.array.length;
var j;
var temp;
for (var i = 1; i < length; i++) {
temp = this.array[i];
j = i;
while (j > 0 && this.array[j - 1] > temp) {
this.array[j] = this.array[j - 1];
j--;
}
this.array[j] = temp;
}
},
//歸并排序
mergeSort: function() {
function mergeSortRec(array) {
var length = array.length;
if (length === 1) {
return array;
}
var mid = Math.floor(length / 2);
var left = array.slice(0, mid);
var right = array.slice(mid, length);
return merge(mergeSortRec(left), mergeSortRec(right));
}
function merge(left, right) {
var result = [];
var il = 0;
var ir = 0;
while (il < left.length && ir < right.length) {
if (left[il] < right[ir]) {
result.push(left[il++]);
} else {
result.push(right[ir++]);
}
}
while (il < left.length) {
result.push(left[il++]);
}
while (ir < right.length) {
result.push(right[ir++]);
}
return result;
}
this.array = mergeSortRec(this.array);
},
//快速排序，參考http://www.ruanyifeng.com/blog/2011/04/quicksort_in_javascript.html
quickSort:function(){
function sort(array){
if (array.length <= 1) {
return array;
}
var pivotIndex = Math.floor(array.length/2);
var pivot = array.splice(pivotIndex,1)[0];
var left = [];
var right = [];
for(var i = 0; i < array.length; i++){
if (array[i] < pivot) {
left.push(array[i]);
}else{
right.push(array[i]);
}
}
return sort(left).concat([pivot],sort(right));
}
this.array = sort(this.array);
}
};
排序方法驗證：
function createNonSortedArray(size) {
var array = new ArrayList();
for (var i = size; i > 0; i--) {
//(function(i) {
array.insert(i);
//})(i);
}
return array;
}
//冒泡排序
var array = createNonSortedArray(5);
console.log(array.toString());
array.bubbleSort();
console.log(array.toString());
//選擇排序
console.log(array.toString());
array.selectionSort();
console.log(array.toString());
//插入排序
console.log(array.toString());
array.insertionSort();
console.log(array.toString());
//歸并排序
console.log(array.toString());
array.mergeSort();
console.log(array.toString());
//快速排序
console.log(array.toString());
array.quickSort();
console.log(array.toString());
源碼地址
Javascript的數(shù)據(jù)結(jié)構(gòu)與算法(三)源碼
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/86659.html
摘要：像剛才的這幅圖，就是二叉搜索樹。而我們本文要學(xué)習(xí)的內(nèi)容，就是如何寫一個二叉搜索樹。但在二叉搜索樹中，我們把節(jié)點成為鍵，這是術(shù)語。前端路漫漫，且行且歌的前端樂園原文鏈接寒假前端學(xué)習(xí)學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法四二叉搜索樹 本系列的第一篇文章: 學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法（一），棧與隊列第二篇文章：學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法（二）：鏈表第三篇文章：學(xué)習(xí)JavaScript數(shù)據(jù)...
摘要：最近想要研究研究地形的渲染，然后就想起了四叉樹，在網(wǎng)上看了一篇相關(guān)的文章，準(zhǔn)備拿實現(xiàn)一下備用。四叉樹的定義是它的每個節(jié)點下至多可以有四個子節(jié)點，通常把一部分二維空間細(xì)分為四個象限或區(qū)域并把該區(qū)域里的相關(guān)信息存入到四叉樹節(jié)點中。 最近想要研究研究webgl地形的渲染，然后就想起了四叉樹，在網(wǎng)上看了一篇相關(guān)的文章，準(zhǔn)備拿javascript實現(xiàn)一下備用。 四叉樹原理 （這部分就直...
摘要：算法性能提升圖片算法處理實質(zhì)原理其實是遍歷像素點，對像素點的值進(jìn)行改造。而像素點的數(shù)量與圖片的大小尺寸成正向指數(shù)級增長，因此適當(dāng)?shù)目s放圖片源后再去處理，對性能的提升十分巨大。 引言： 本系列現(xiàn)在構(gòu)思成以下4個部分: 基礎(chǔ)類型圖片處理技術(shù)之縮放、裁剪與旋轉(zhuǎn)(傳送門)； 基礎(chǔ)類型圖片處理技術(shù)之圖片合成(傳送門)； 基礎(chǔ)類型圖片處理技術(shù)之文字合成(傳送門)； 算法類型圖片處理技術(shù)(傳送門)...
閱讀 2978·2021-11-25 09:43
閱讀 3600·2021-11-24 11:13
閱讀 3373·2021-10-14 09:42
閱讀 2578·2021-09-23 11:53
閱讀 3622·2021-09-22 15:57
閱讀 3233·2021-09-02 09:54
閱讀 3510·2019-08-30 13:47
閱讀 1650·2019-08-29 16:55
