資訊專欄INFORMATION COLUMN
摘要：快速排序，參考排序算法的完整實現各種排序算法的完整實現如下冒泡排序選擇排序插入排序歸并排序快速排序，參考排序方法驗證冒泡排序選擇排序插入排序歸并排序快速排序源碼地址的數據結構與算法三源碼
1 排序和搜索算法 1.1 排序算法 1.1.1 冒泡排序
冒泡排序比較任何兩個相鄰的項,如果第一個比第二個大,則交換它們。元素項向上移動至正確的順序,就好像氣泡升至表面一樣,冒泡排序因此得名。冒泡排序的時間復雜度為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 選擇排序
選擇排序算法是一種原址比較排序算法。選擇排序大致的思路是找到數據結構中的最小值并將其放置在第一位,接著找到第二小的值并將其放在第二位,以此類推。選擇排序的時間復雜度為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 插入排序
有一個已經有序的數據序列，要求在這個已經排好的數據序列中插入一個數，但要求插入后此數據序列仍然有序，這個時候就要用到一種新的排序方法——插入排序法,插入排序的基本操作就是將一個數據插入到已經排好序的有序數據中，從而得到一個新的、個數加一的有序數據，算法適用于少量數據的排序，時間復雜度為O(n^2)。是穩定的排序方法。插入排序的基本思想是：每步將一個待排序的紀錄，按其關鍵碼值的大小插入前面已經排序的文件中適當位置上，直到全部插入完為止。
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）的一個非常典型的應用。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為二路歸并。時間復雜度為O(nlogn)，空間復雜度為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 快速排序
通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然后再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。時間負責度為O(n^2)，并且比其他負責度為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 排序算法的完整實現
各種排序算法的完整實現如下：
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的數據結構與算法(三)源碼
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/86659.html
摘要：像剛才的這幅圖，就是二叉搜索樹。而我們本文要學習的內容，就是如何寫一個二叉搜索樹。但在二叉搜索樹中，我們把節點成為鍵，這是術語。前端路漫漫，且行且歌的前端樂園原文鏈接寒假前端學習學習數據結構與算法四二叉搜索樹 本系列的第一篇文章: 學習JavaScript數據結構與算法（一），棧與隊列第二篇文章：學習JavaScript數據結構與算法（二）：鏈表第三篇文章：學習JavaScript數據...
摘要：最近想要研究研究地形的渲染，然后就想起了四叉樹，在網上看了一篇相關的文章，準備拿實現一下備用。四叉樹的定義是它的每個節點下至多可以有四個子節點，通常把一部分二維空間細分為四個象限或區域并把該區域里的相關信息存入到四叉樹節點中。 最近想要研究研究webgl地形的渲染，然后就想起了四叉樹，在網上看了一篇相關的文章，準備拿javascript實現一下備用。 四叉樹原理 （這部分就直...
摘要：算法性能提升圖片算法處理實質原理其實是遍歷像素點，對像素點的值進行改造。而像素點的數量與圖片的大小尺寸成正向指數級增長，因此適當的縮放圖片源后再去處理，對性能的提升十分巨大。 引言： 本系列現在構思成以下4個部分: 基礎類型圖片處理技術之縮放、裁剪與旋轉(傳送門)； 基礎類型圖片處理技術之圖片合成(傳送門)； 基礎類型圖片處理技術之文字合成(傳送門)； 算法類型圖片處理技術(傳送門)...
閱讀 2969·2021-11-25 09:43
閱讀 3586·2021-11-24 11:13
閱讀 3354·2021-10-14 09:42
閱讀 2556·2021-09-23 11:53
閱讀 3605·2021-09-22 15:57
閱讀 3221·2021-09-02 09:54
閱讀 3499·2019-08-30 13:47
閱讀 1638·2019-08-29 16:55
