js 实现排序算法
2019-02-23 本文已影响0人
安石0
1：桶排序
var a=[1,2,89,23,79,45,33];
var brr=[];
for(var i=0;i<a.length;i++){
brr[a[i]]=0
}
var crr=[]
brr.forEach(function(arr,index){
crr.push(index)
})
2：冒泡排序
var arr=[5,123,333,99992,21,]
console.log(arr)
var len=arr.length
for(var j=0;j<len;j++){
//len-j还剩下多少个没有排，每次都把最大放在len-i-1位
for(var i=1;i<len-j;i++){
if(arr[i-1]>arr[i]){
min=arr[i]
arr[i]=arr[i-1]
arr[i-1]=min
}
}
}
console.log(arr)
3：选择排序
思想：把最小的放在第一位
选择剩下的：把最小的放在第一位
var arr=[5,4,3,2,1,0]
for(var i=0;i<arr.length;i++){
var minIndex=i
for(var j=i+1;j<arr.length;j++){
if(arr[j]<arr[minIndex]){
minIndex=j;//找到i后面位置的索引
}
}
temp = arr[i];//存储当前i对应的值arr[i]
arr[i] = arr[minIndex];//将剩下的最小的值复制给arr[i]
arr[minIndex] = temp;//不改数组的值
}
4、快速排序
原理：
（1）在数据集之中，选择一个元素作为"基准"（pivot）。
（2）所有小于"基准"的元素，都移到"基准"的左边；所有大于"基准"的元素，都移到"基准"的右边。
（3）对"基准"左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。
var a=[2,4,7,1,2,0,1111,54]
function sort(arr){
if (arr.length <= 1) { return arr; }//必须的，如果数组只剩一位就没有必要了
var pivotIndex = Math.floor(arr.length / 2) ;
var pivot = arr.splice(pivotIndex, 1)[0];
var left = [];
var right = [];
for(var i=0;i<arr.length;i++){
if(arr[i]>pivot){
right.push(arr[i])
}
else{
left.push(arr[i])
}
}
return sort(left).concat([pivot],sort(right))
}
5、基数排序
radixSort.gif
var a = [5, 4, 13, 2, 1, 0]
function radivSort(arr) {
var digits = (Math.max.apply(null, arr) + '').length
var arr1;
for (var l = 1; l < digits+1; l++) {
console.log('最大位数为：'+l)
var b = []
for (var i = 0; i < 10; i++) { //初始化b的值
b[i] = []
}
for (var i = 0; i < arr.length; i++) {
if ((arr[i] + '').length - l < 0) {
b[0].push(arr[i])
} else {
k = (arr[i] + '')
k = k[k.length - l]
for (var j = 0; j < b.length; j++) {
if (k == j) {
b[j].push(arr[i])
}
}
}
}
var arr=[]
for(var i=0;i<b.length;i++){
for(var j=0;j<b[i].length;j++){
arr.push(b[i][j])
}
}
arr1=arr
}
return arr1
}
radivSort(a)
/*
var b=[]//记录某位的数字（比如记录个位的数值）
for(var i=0;i<10;i++){
b[i]=[]
}
for(var i=0;i<a.length;i++){
k=(a[i]+'')
k=k[k.length-1]
for(var j=0;j<b.length;j++){
if(k==j){
b[j].push(a[i])
}
}
}
var a1=[]
for(var i=0;i<b.length;i++){
for(var j=0;j<b[i].length;j++){
a1.push(b[i][j])
}
}
var b1=[]
for(var i=0;i<10;i++){
b1[i]=[]
}
for(var i=0;i<a1.length;i++){
if((a1[i]+'').length-2<0){
b1[0].push(a1[i])
}
k=(a1[i]+'')
k=k[k.length-2]
//console.log(k)
for(var j=0;j<b1.length;j++){
if(k==j){
b1[j].push(a1[i])
}
}
}
var a2=[]
for(var i=0;i<b1.length;i++){
for(var j=0;j<b1[i].length;j++){
a2.push(b1[i][j])
}
}
var b2=[]
for(var i=0;i<10;i++){
b2[i]=[]
}
for(var i=0;i<a2.length;i++){
if((a2[i]+'').length-3<0){
b2[0].push(a2[i])
}
k=(a2[i]+'')
k=k[k.length-3]
//console.log(k)
for(var j=0;j<b2.length;j++){
if(k==j){
b2[j].push(a1[i])
}
}
}
var a3=[]
for(var i=0;i<b2.length;i++){
for(var j=0;j<b2[i].length;j++){
a3.push(b2[i][j])
}
}
var b3=[]
for(var i=0;i<10;i++){
b3[i]=[]
}
for(var i=0;i<a3.length;i++){
if((a3[i]+'').length-4<0){
b3[0].push(a3[i])
}
k=(a3[i]+'')
k=k[k.length-4]
//console.log(k)
for(var j=0;j<b3.length;j++){
if(k==j){
b3[j].push(a1[i])
}
}
}
var a4=[]
for(var i=0;i<b3.length;i++){
for(var j=0;j<b3[i].length;j++){
a4.push(b3[i][j])
}
}
console.log(a)
console.log(b)
console.log(a1)
console.log(b1)
console.log(a2)
console.log(b2)
console.log(a3)
console.log(b3)
console.log(a4)
*/
6，归并排序
二分法，分而治之
function merge(left, right){
let result = []
let li = 0
let ri = 0
while(li < left.length && ri < right.length){
if (left[li] < right[ri]) {
result.push(left[li++])
} else {
result.push(right[ri++])
}
}
while(li < left.length){
result.push(left[li++])
}
while(ri < left.length){
result.push(left[ri++])
}
console.log('result:',result)
return result
}
function mergeSortRec(arr = [8,7,6,5,4,3,2,1]) {
let len = arr.length
if (len === 1) {
return arr
}
let mid = Math.floor(len / 2)
let left = arr.slice(0, mid)
let right = arr.slice(mid, len)
console.log('left:', left)
console.log('right:', right)
return merge(mergeSortRec(left), mergeSortRec(right))
}
mergeSortRec()
7, 堆排序
7.1 算法描述
- 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
- 将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
- 由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。
大白话:将待排序的构建成树，第一个做丐帮帮主(根节点)，其余依次拍下来，好现在很开始帮主自由选拔啦，武功最高的在根节点，现在把帮主贬任期满了，不能再次参选的，最小的成为代理帮主，竞争人数减少一个，
重复，直到只剩最后一个人。
let arr = [1,3,2,5,4,7,6,8,9]
function heapSort (arr) {
let len // 数组的长度
function heapify (arr, i) {
// i 为父节点
let left = 2 * i + 1
let right = 2 * i + 2
let largest = i
if (left < len && arr[left] > arr[largest]) {
largest = left
}
if (right < len && arr[right] > arr[largest]) {
largest = right
}
if (largest !== i) {
swap(arr, i, largest)
// 要把最小的打到最下面
heapify(arr, largest)
}
}
function swap (arr, a, b) {
[arr[a], arr[b]] = [arr[b], arr[a]]
}
// 构建最大堆 最大值在顶上
function buildMaxHeap(arr) {
len = arr.length
// 因为左右叶子节点为2*i+1 和 2*i+2
for (let i = Math.floor(len/2) ; i >= 0 ; i--) {
heapify(arr, i)
}
}
buildMaxHeap(arr)
// 只剩最后一个的时候不需要操作了
for (let i = arr.length -1; i > 0 ; i --) {
swap(arr, 0, i) // 把最大的放到最后面，树的长度减少1
len--
heapify(arr, 0) // 群龙无首，重新竞争吧
}
return arr
}
console.log(heapSort(arr))
8 计数排序
count1.jpg
count2.jpg
arr = [9,2,1,2,3,4,7]
var countSort = function(array) {
var i, z = 0, count = [],
min = Math.min.apply({}, array), // 1
max = Math.max.apply({}, array), // 9
size = array.length;
//给新数组预填为零
for (i = min; i <= max; i++) {
count[i] = 0; // [,0,0,0, 0,0,0, 0,0,0]
}
for (i=0; i < size; i++) {
count[array[i]]++;
}
for (i = min; i <= max; i++) {
while (count[i]-- > 0) {//循环新数组，如果不为零，则把i返回array
array[z++] = i;
}
}
return array;
}
