数据结构与算法(排序) --javascript语言描述
冒泡排序
从数组中第一个数开始,依次遍历数组中的每一个数,通过相邻比较交换,每一轮循环下来找出剩余未排序数的中的最大数并”冒泡”至数列的顶端。
function bubbleSort(arr) { for (var i = 0; i < arr.length - 1 ; i++) { for (var j = 0; j < arr.length - i - 1 ; j++) { if (arr[j] > arr[j+1]) { //相邻元素两两对比 let temp = arr[j+1]; //元素交换 arr[j+1] = arr[j]; arr[j] = temp; } } } return arr; } console.log(bubbleSort([72,54,58,30,31,78,2,77,82,72]))
最佳情况:输入数组按升序排列。 T(n) = O(n)
最差情况:输入数组按降序排列。 T(n) = O(n2)
平均情况:T(n) = O(n2)
稳定性:稳定
选择排序
从所有记录中选出最小的一个数据元素与第一个位置的记录交换;然后在剩下的记录当中再找最小的与第二个位置的记录交换,循环到只剩下最后一个数据元素为止。
function selectionSort(arr) { let minIndex,temp; for (let i = 0; i < arr.length-1; i++) { minIndex = i; for (let j = i+1; j < arr.length; j++) { if(arr[j] < arr[minIndex]) { minIndex = j; } } temp = arr[i]; arr[i]=arr[minIndex]; arr[minIndex]=temp; } return arr; } console.log(selectionSort([72,54,58,30,31,78,2,77,82,72]))
最佳情况:T(n) = O(n2)
最差情况:T(n) = O(n2)
平均情况:T(n) = O(n2)
稳定性:不稳定
插入排序
从待排序的n个记录中的第二个记录开始,依次与前面的记录比较并寻找插入的位置,每次外循环结束后,将当前的数插入到合适的位置。
function insertionSort(arr) { for (let i = 1; i < arr.length; i++) { let key = arr[i]; let j = i - 1; while (j>=0 && arr[j] > key) { arr[j+1] = arr[j]; j--; } arr[j+1] = key; } return arr; } console.log(insertionSort([6,10,0,6,5,8,7,4,2,7]))
最佳情况:输入数组按升序排列。T(n) = O(n)
最坏情况:输入数组按降序排列。T(n) = O(n2)
平均情况:T(n) = O(n2)
稳定性:稳定
希尔排序
Shell排序法是对相邻指定距离(称为增量)的元素进行比较,并不断把增量缩小至1,完成排序。
function shellSort(arr) { var len = arr.length, temp, gap = 1; while(gap < len/5) { //动态定义间隔序列 gap =gap*5+1; } for (gap; gap > 0; gap = Math.floor(gap/5)) { for (var i = gap; i < len; i++) { temp = arr[i]; for (var j = i-gap; j >= 0 && arr[j] > temp; j-=gap) { arr[j+gap] = arr[j]; } arr[j+gap] = temp; } } return arr; } var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]; console.log(shellSort(arr));
最佳情况:T(n) = O(nlog2 n)
最坏情况:T(n) = O(nlog2 n)
平均情况:T(n) =O(nlog n)
稳定性:不稳定
归并排序
归并排序是分治法(Divide and Conquer)的一个典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。
function mergeSort(arr) { if(arr.length < 2) { return arr; } let middle = Math.floor(arr.length/2); let left = arr.slice(0,middle); let right = arr.slice(middle); return merge(mergeSort(left),mergeSort(right)); } function merge(left,right) { let res = []; while(left.length && right.length) { if(left[0] <= right[0]) { res.push(left.shift()); } else { res.push(right.shift()); } } while(left.length) { res.push(left.shift()); } while(right.length) { res.push(right.shift()); } return res; } let arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]; console.log(mergeSort(arr));
最佳情况:T(n) = O(n)
最差情况:T(n) = O(nlogn)
平均情况:T(n) = O(nlogn)
稳定性:稳定
快速排序
1.从待排序的n个记录中任意选取一个记录(通常选取第一个记录)为分区标准;
2.把所有小于该排序列的记录移动到左边,把所有大于该排序码的记录移动到右边,中间放所选记录,称之为第一趟排序;
3.然后对前后两个子序列分别重复上述过程,直到所有记录都排好序。
方法一:
function quickSort(arr,left,right) { let i = left; let j = right; let temp = 0; if(i < j) { //待排序的元素至少有两个的情况 temp = arr[i]; //待排序的第一个元素作为基准元素 while(i != j) { //从左右两边交替扫描,直到i = j while(j > i && arr[j] >= temp) { j --; //从右往左扫描,找到第一个比基准元素小的元素 } arr[i] = arr[j]; //找到这种元素arr[j]后与arr[i]交换 while(i < j && arr[i] <= temp) { i ++; //从左往右扫描,找到第一个比基准元素大的元素 } arr[j] = arr[i]; //找到这种元素arr[i]后,与arr[j]交换 } arr[i] = temp; //基准元素归位 quickSort(arr,left,i-1); //对基准元素左边的元素进行递归排序 quickSort(arr,i+1,right); //对基准元素右边的进行递归排序 } return arr; } let arr = [5,7,1,8,4] console.log(quickSort(arr,0,arr.length-1));
方法二:
function quickSort(arr) { if(arr.length <= 1) { return arr; } let middleIndex = Math.floor(arr.length/2); let middle = arr.splice(middleIndex,1)[0];//选取基准值 并从数组中删除 let left = []; //小于middle的数组 let right = []; //大于middle的数组 for (var i = 0; i < arr.length; i++) { if(arr[i] < middle) { left.push(arr[i]); } else { right.push(arr[i]); } } return quickSort(left).concat([middle],quickSort(right)); } let arr = [5,7,1,8,4] console.log(quickSort(arr));
最佳情况:T(n) = O(nlogn)
最差情况:T(n) = O(n2)
平均情况:T(n) = O(nlogn)
稳定性:不稳定