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
网友评论