常用排序算法学习

常用排序算法学习:
程序员各种排序算法,算法的实现和分析

排序算法的分类

  1. 排序分内排序和外排序。
  2. 内排序:指在排序期间数据对象全部存放在内存的排序。
  3. 外排序:指在排序期间全部对象个数太多,不能同时存放在内存,必须根据排序过程的要求,不断在内、外存之间移动的排序。
  4. 内排序的方法有许多种,按所用策略不同,可归纳为五类:插入排序、选择排序、交换排序、归并排序、分配排序和计数排序。
  5. 插入排序主要包括直接插入排序,折半插入排序和希尔排序两种;
  6. 选择排序主要包括直接选择排序和堆排序;
  7. 交换排序主要包括冒泡排序和快速排序;
  8. 归并排序主要包括二路归并(常用的归并排序)和自然归并。
  9. 分配排序主要包括箱排序和基数排序

冒泡排序

  • 冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较,交换也发生在这两个元素之间。所以,如果两个元素相等,是不用交换的;如果两个相等的元素没有相邻,那么即使通过前面的两两交换把两个相邻起来,这时候也不会交换,所以相同元素的前后顺序并没有改变,所以冒泡排序是一种稳定排序算法
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    // js代码
    function sort(arr) {
    if (arr.length == 0) {
    return [];
    }
    var length = arr.length;
    for (var i = 0; i < length; i++) {
    for (var j = 0; j < length - i - 1; j++) {
    if (arr[j] > arr[j + 1]) {
    var temp = arr[j];
    arr[j] = arr[j + 1];
    arr[j + 1] = temp;
    console.log(arr);
    }
    }
    }
    }

快速排序

  • 快速排序是对冒泡排序的一种改进。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列.
  • 时间复杂度:O(nlgn)最坏:O(n^2)空间复杂度:O(nlgn)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// js递归实现
function quickSort(arr) {
if (arr.length == 0) {
return [];
}
var left = [];
var right = [];
var pivot = arr[0];
for (var i = 1; i < arr.length; i++) {
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return quickSort(left).concat(pivot, quickSort(right));
}
var a = [];
for (var i = 0; i < 10; ++i) {
a[i] = Math.floor((Math.random() * 100) + 1);
}
console.log(a);
console.log(quickSort(a));

直接插入排序

  • 直接插入排序(straight insertion sort)的作法是:每次从无序表中取出第一个元素,把它插入到有序表的合适位置,使有序表仍然有序.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function insertionSort(arr) {
var temp, inner;
for (var outer = 1; outer <= arr.length - 1; ++outer) {
temp = arr[outer];
inner = outer;
while (inner > 0 && (arr[inner - 1] >= temp)) {
arr[inner] = arr[inner - 1];
--inner;
}
arr[inner] = temp;
}
return arr;
}
var a = [];
for (var i = 0; i < 10; ++i) {
a[i] = Math.floor((Math.random() * 100) + 1);
}
console.log(a);
console.log(insertionSort(a));

折半插入排序

  • 折半插入排序算法的具体操作为:在将一个新元素插入已排好序的数组的过程中,寻找插入点时,将待插入区域的首元素设置为a[low],末元素设置为 a[high],则轮比较时将待插入元素与a[m],其中m=(low+high)/2相比较,如果比参考元素小,则选择a[low]到a[m-1]为新 的插入区域(即high=m-1),否则选择a[m+1]到a[high]为新的插入区域(即low=m+1),如此直至low<=high不成 立,即将此位置之后所有元素后移一位,并将新元素插入a[high+1]

希尔排序

  • 先取一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插入 排序;然后,取第二个增量d2<d1重复上述的分组和排序,直至所取的增量dt=1(dt<dt-l<…<d2<d1), 即所有记录放在同一组中进行直接插入排序为止。
  • 该方法实质上是一种分组插入方法。插入排序(Insertion Sort)的一个重要的特点是,如果原始数据的大部分元素已经排序,那么插入排序的速度很快(因为需要移动的元素很少)。从这个事实我们可以想到,如果原 始数据只有很少元素,那么排序的速度也很快。--希尔排序就是基于这两点对插入排序作出了改进。

直接选择排序

  • 直接选择排序是给每个位置选择当前元素最小的,比如给第一个位置选择最小的,在剩余元素里面给第二个元素选择第二小的,依次类推,直到第n-1个元素,第n个 元素不用选择了,因为只剩下它一个最大的元素了。那么,在一趟选择,如果当前元素比一个元素小,而该小的元素又出现在一个和当前元素相等的元素后面,那么 交换后稳定性就被破坏了。比较拗口,举个例子,序列5 8 5 2 9,我们知道第一遍选择第1个元素5会和2交换,那么原序列中2个5的相对前后顺序就被破坏了,所以选择排序不是一个稳定的排序算法。时间复杂度是O(n^2)

堆排序

  • 我们知道堆的结构是节点i的孩子为2i和2i+1节点,大顶堆要求父节点大于等于其2个子节点,小顶堆要求父节点小于等于其2个子节点。在一个长为n 的序列,堆排序的过程是从第n/2开始和其子节点共3个值选择最大(大顶堆)或者最小(小顶堆),这3个元素之间的选择当然不会破坏稳定性。但当为n /2-1, n/2-2, …1这些个父节点选择元素时,就会破坏稳定性。有可能第n/2个父节点交换把后面一个元素交换过去了,而第n/2-1个父节点把后面一个相同的元素没 有交换,那么这2个相同的元素之间的稳定性就被破坏了。所以,堆排序不是稳定的排序算法。

二路归并排序

  • 归并排序是把序列递归地分成短序列,递归出口是短序列只有1个元素(认为直接有序)或者2个序列(1次比较和交换),然后把各个有序的段序列合并成一个有 序的长序列,不断合并直到原序列全部排好序。可以发现,在1个或2个元素时,1个元素不会交换,2个元素如果大小相等也没有人故意交换,这不会破坏稳定 性。那么,在短的有序序列合并的过程中,稳定是是否受到破坏?没有,合并过程中我们可以保证如果两个当前元素相等时,我们把处在前面的序列的元素保存在结 果序列的前面,这样就保证了稳定性。所以,归并排序也是稳定的排序算法。
文章目录
  1. 1. 排序算法的分类
  2. 2. 冒泡排序
  3. 3. 快速排序
  4. 4. 直接插入排序
  5. 5. 折半插入排序
  6. 6. 希尔排序
  7. 7. 直接选择排序
  8. 8. 堆排序
  9. 9. 二路归并排序
Error: Comments Not Initialized
,