2019-09-09 排序算法 JavaScript实现
1、快速排序
快速排序的原理是：
每次将一个元素找到它的位置，同时将比它大的元素丢一边，将比它小的元素丢一边。
我们假设第一个元素在排序完成后应该位于红线位置，那么我们同时从两边开始比较，先取第一个元素，作为待比较元素，把它保存在一个额外的变量里，现在它的位置就空出来了：
然后从倒数第一个元素开始与待排序元素比较，如果指针所指的元素（绿色箭头）大于待排序元素，不用管，左移指针，一直重复这个步骤，直到遇到一个比待排序元素小的元素：
将它丢到左边的空位置里去：
然后，左边的指针往右移动，如果遇到比待排序元素大的元素：
将其右丢：
然后向左移动右边的指针，重复上述步骤，直到两个指针相遇：
说明一个待排序元素找到了它的位置，后面递归前面的步骤即可。
JavaScript实现：
var arr = [10,8,6,4,2,1,3,5,7,9,0];
for(let i=0,len = arr.length; i<len;i++)
arr[i] = Math.round(Math.random()*100);
console.log(arr);
function quickSort(arr,left,right)
{
var left_keep = left, right_keep = right;
if(right > left)
{
var one = arr[left];
let left_move = false;
while(left < right)
{
if(left_move){
if(arr[left] < one){
left++;
}
else{
arr[right] = arr[left];
left_move = false;
right--;
}
}
else{
if(arr[right] > one){
right--;
}
else{
arr[left] = arr[right];
left_move = true;
left++;
}
}
}
arr[left] = one;
console.log(arr.toString(),"待排序元素："+one,"中界线："+left);
//递归调用
if(left-1 > left_keep){ //只要还有两个或多余两个元素
console.log("左边递归");
quickSort(arr,left_keep,left-1);
}
if(right+1 < right_keep){
console.log("右边递归");
quickSort(arr,right+1,right_keep);
}
}
}
quickSort(arr,0,10);
参考：生成随机数：
https://www.cnblogs.com/starof/p/4988516.html
2、冒泡排序
冒泡排序比较简单，JavaScript实现如下：
var arr = [10,8,6,4,2,1,3,5,7,9,0]; //直接使用或随机生成数组进行测试
for(let i=0,len = arr.length; i<len;i++)
arr[i] = Math.round(Math.random()*100);
console.log(arr);
function bubleSort(arr)
{
for(let i=0,j=arr.length-1;i< j;i++) //第一层循环，是趟数 循环 趟数比元素个数少1
{
for(let k=0;k < j-i;) //第二次循环 ，是每趟中的元素循环 k最多取值到倒数第2个下标
{
if( arr[k] > arr[++k] )
{
let temp = arr[k-1];
arr[k-1] = arr[k];
arr[k] = temp;
}
}
}
}
bubleSort(arr);
console.log(arr);
3、选择排序
基本思想是每次从待排序的一堆元素中，找到最小的，放到已排序的一堆元素的最后。
var arr = [10,8,6,4,2,1,3,5,7,9,0];
for(let i=0,len = arr.length; i<len;i++)
arr[i] = Math.round(Math.random()*100);
console.log(arr);
function selectionSort(arr)
{
for(let i=0,j=arr.length-1;i< j;i++) //i代表待填充的位置
{
let min_index=i;
for(let k=i+1;k <= j;k++)
{
if( arr[k] < arr[min_index] )
{
min_index = k;
}
}
let temp = arr[i];
arr[i] = arr[min_index];
arr[min_index] = temp;
console.log(temp,arr[i],arr.toString());
}
}
selectionSort(arr);
console.log(arr);
4、插入排序
基本思想是每次从待排序的一堆元素取出第一个，把它插入到已经派好序的一堆元素中。
我们假设指针1所指的元素是已排好序的一堆元素中的最后一个，指针2就是每次待插入的元素，我们每次保存待插入元素到一个变量中：
然后将它们进行比较，如果指针2所指元素小于指针1所指元素：
则将元素后移，并将指针1左移：
因为指针1找不到元素了，所以将保存的待插入元素的值，赋值给第一个元素：
下一轮，指针1、2的开始位置如图：
然后重复上一轮的步骤。
var arr = [10,8,6,4,2,1,3,5,7,9,0];
for(let i=0,len = arr.length; i<len;i++)
arr[i] = Math.round(Math.random()*100);
console.log(arr);
function insertionSort(arr)
{
for(let i=1,j=arr.length;i< j;i++)
{
let k = i-1;
let temp = arr[i];
while( temp < arr[k--] && k>-2){
arr[k+2] = arr[k+1]; console.log("当前值小于已排序值" +arr[k+1]);
}
arr[k+2] = temp;
console.log("排序一轮： ",arr.toString());
}
}
insertionSort(arr);
console.log(arr);
5、希尔排序
希尔排序是插入排序的改进，它把待排序的元素分成几个组来排序，然后多次按不同间距来分组，直到达到所有元素最后只分成一个组。
分组方法有多种，其中一种：我们最开始把两个元素分为一组（共n/2组）：
然后在每组内进行插入排序，排序完成后，继续按新的间距分组，组内元素增加：
直到最后，将所有元素视为一个组，
6
7
8
