Libx

几种排序

字数统计: 1,124阅读时长: 5 min
2018/01/02 Share

学习数据结构,最后接触了很多关于排序的东西。一些比较常见且使用较多的排序来总结一下。另外那些牛X的排序感觉理解还是有些难度的。。下面来写一下各种排序的JS实现。

先上一张图:

冒泡排序

冒泡排序应该可以说是我接触的第一个排序算法,也是一种思想很容易理解的算法。

思想:

相邻的数据进行两两比较,小数放在前面,大数放在后面,一趟下来,最小的数被排在了第一位,第二趟也是如此,如此类推,直到所有的数据排序完成

代码实现:

function bubbleSort(arr) {
var len = arr.length;
for (var i = 0; i < len; i++) {
for (var j = 0; j < len - 1 - i; j++) {
if (arr[j] > arr[j+1]) { //相邻元素两两对比
var temp = arr[j+1]; //元素交换
arr[j+1] = arr[j];
arr[j] = temp;
}
}
}
return arr;
}

选择排序

在时间复杂度上表现最稳定的排序算法之一,因为无论什么数据进去都是O(n²)的时间复杂度。。。所以用到它的时候,数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

思想:

先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

实现:

function selectionSort(arr) {
var len = arr.length;
var minIndex, temp;
for (var i = 0; i < len - 1; i++) {
minIndex = i;
for (var j = i + 1; j < len; j++) {
if (arr[j] < arr[minIndex]) { //寻找最小的数
minIndex = j; //将最小数的索引保存
}
}
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
return arr;
}

插入排序

思想

将数据分为两部分,有序部分与无序部分,一开始有序部分包含第1个元素,依次将无序的元素插入到有序部分,直到所有元素有序。插入排序又分为直接插入排序、二分插入排序、链表插入等,这里只讨论直接插入排序。它是稳定的排序算法,时间复杂度为O(n^2)

实现:

function insertionSort(arr) {
var len = arr.length;
var preIndex, current;
for (var i = 1; i < len; i++) {
preIndex = i - 1;
current = arr[i];
while(preIndex >= 0 && arr[preIndex] > current) {
arr[preIndex+1] = arr[preIndex];
preIndex--;
}
arr[preIndex+1] = current;
}
return arr;
}

希尔排序(Shell Sort)

#### 思想:
希尔排序是插入排序的一种更高效率的实现。它与插入排序的不同之处在于,它会优先比较距离较远的元素。希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列,也可以动态的定义间隔序列。

实现:

function shellSort(arr) {
var len = arr.length,
temp,
gap = 1;
while(gap < len/3) { //动态定义间隔序列
gap =gap*3+1;
}
for (gap; gap> 0; gap = Math.floor(gap/3)) {
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;
}

快速排序

思想

快速排序是目前在实践中非常高效的一种排序算法,它不是稳定的排序算法,平均时间复杂度为O(nlogn),最差情况下复杂度为O(n^2)。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

最基本:

//快速排序
function quickSort(arr,left,right){
{
if (left < right)
{
let i = left, j = right, x = arr[left];
while (i < j)
{
while(i < j && arr[j] >= x)
j--;
if(i < j)
arr[i++] = arr[j];
while(i < j && arr[i] < x)
i++;
if(i < j)
arr[j--] = arr[i];
}
arr[i] = x;
quick_sort(arr, left, i - 1); // 递归调用
quick_sort(arr, i + 1, right);
}
}

改进一:

function quickSort(arr,left,right){
if(left<right){
let x = arr[right], i = left-1, temp
for(let j = left; j<=right;j++){
if(arr[j]<=x){
i++
temp = arr[i]
arr[i]=arr[j]
arr[j]=temp
}
}
quickSort(arr, left, i-1)
quickSort(arr, i+1, right)
}
return arr
}

改进二:

function quickSort (arr){
if(arr.length <=1){
return arr
} else{
let pivotIndex = Math.floor(arr.length/2)
let pivot =arr.splice(pivotIndex,1)[0]
let left =[]
let right =[]
for(let i=0;i<arr.length;i++){
if(arr[i]<pivot){
left.push(arr[i])
}else{
right.push(arr[i])
}
}
return quickSort(left).concat([pivot],quickSort(right))
}
}

CATALOG
  1. 1. 冒泡排序
    1. 1.1. 思想:
    2. 1.2. 代码实现:
  2. 2. 选择排序
    1. 2.1. 思想:
    2. 2.2. 实现:
  3. 3. 插入排序
    1. 3.1. 思想
    2. 3.2. 实现:
  4. 4. 希尔排序(Shell Sort)
    1. 4.1. 实现:
  5. 5. 快速排序
    1. 5.1. 思想
    2. 5.2. 最基本:
    3. 5.3. 改进一:
    4. 5.4. 改进二: