1 | * 利用栈来做数制转换 |
csskr。
1 | * 利用栈来做数制转换 |
1 | 快速排序是一个就地排序,分而治之,大规模递归的算法。从本质上来说,它是归并排序的就地版本。快速排序可以由下面四步组成。 |
1 | 归并排序先分解要排序的序列,从1分成2,2分成4,依次分解,当分解到只有1个一组的时候,就可以排序这些分组, |
1 | 堆排序适合于数据量非常大的场合(百万数据)。 |
1 | Shell排序通过将数据分成不同的组,先对每一组进行排序,然后再对所有的元素进行一次插入排序,以减少数据交换和移动的次数。 |
1 | 插入排序通过把序列中的值插入一个已经排序好的序列中,直到该序列的结束。插入排序是对冒泡排序的改进。它比冒泡排序快2倍。 |
1 | 冒泡排序是最慢的排序算法。在实际运用中它是效率最低的算法。它通过一趟又一趟地比较数组中的每一个元素,使较大的数据下沉, |
1 | 这两种排序方法都是交换方法的排序算法,效率都是 O(n2)。在实际应用中处于和冒泡排序基本相同的地位。 |
1 | 基数排序和通常的排序算法并不走同样的路线。它是一种比较新颖的算法,但是它只能用于整数的排序, |
排序法 | 平均时间 | 最差情形 | 稳定度 | 额外空间 | 备注 |
---|---|---|---|---|---|
冒泡排序 | O(nlogn) | O(n2) | 稳定 | O(1) | 效率最低,n很小时可以使用,一般不用 |
选择排序 | O(nlogn) | O(n2) | 不稳定 | O(1) | 效率很低,n很小时可以使用,一般不用 |
插入排序 | O(nlogn) | O(n2) | 稳定 | O(1) | 大部分已排序时比较好 |
希尔排序 | O(nlogn) | O(n的s次方) | 不稳定 | O(1) | 1<s<2 |
快速排序 | O(nlogn) | O(n2) | 不稳定 | O(nlogn) | 数据量很大时好,平均效率最高的算法 |
归并排序 | O(nlogn) | O(nlogn) | 稳定 | O(1) | 数据量很大时好 |
堆排序 | O(nlogn) | O(nlogn) | 不稳定 | O(1) | 数据量很大时好 |
1 | var generateTestData = require('https://21cm.js.org/lib/TestDataGenerator'); |
1 | var generateTestData = require('https://21cm.js.org/lib/TestDataGenerator') |
1 | var generateTestData = require('https://21cm.js.org/lib/TestDataGenerator'); |
1 | var generateTestData = require('https://21cm.js.org/lib/TestDataGenerator'); |
1 | var generateTestData = require('https://21cm.js.org/lib/TestDataGenerator'); |
1 | var generateTestData = require('https://21cm.js.org/lib/TestDataGenerator'); |
1 | 快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高,因此经常被采用,而且快速排序思想----分治法也确实实用! |
快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略,通常称其为分治法(Divide-and-ConquerMethod)。
该方法的基本思想是:1
2
3
4
51.先从数列中取出一个数作为基准数。
2.分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边。
3.再对左右区间重复第二步,直到各区间只有一个数。
虽然快速排序称为分治法,但分治法这三个字显然无法很好的概括快速排序的全部步骤。
对快速排序作了进一步的说明:挖坑填数
+分治法
:
index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|---|
72 | 6 | 57 | 88 | 60 | 42 | 83 | 73 | 48 | 85 |
1 | 以一个数组作为示例,取区间第一个数为基准数。 |
index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|---|
48 | 6 | 57 | 88 | 60 | 42 | 83 | 73 | 88 | 85 |
数组变为上述这样。 i = 3; j = 7; X=72
1 | 再重复上面的步骤,先从后向前找,再从前向后找。 |
index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|---|
48 | 6 | 57 | 42 | 60 | 72 | 83 | 73 | 88 | 85 |
可以看出a[5]前面的数字都小于它,a[5]后面的数字都大于它。因此再对a[0…4]和a[6…9]这二个子区间重复上述步骤就可以了。
1 | 1.i =L; j = R; 将基准数挖出形成第一个坑a[i]。 |
照着这个总结很容易实现挖坑填数的代码:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26int AdjustArray(int s[], int l, int r) //返回调整后基准数的位置
{
int i = l, j = r;
int x = s[l]; //s[l]即s[i]就是第一个坑
while (i < j)
{ // 从右向左找小于x的数来填s[i]
while(i < j && s[j] >= x)
j--;
if(i < j)
{
s[i] = s[j]; //将s[j]填到s[i]中,s[j]就形成了一个新的坑
i++;
}
// 从左向右找大于或等于x的数来填s[j]
while(i < j && s[i] < x)
i++;
if(i < j)
{
s[j] = s[i]; //将s[i]填到s[j]中,s[i]就形成了一个新的坑
j--;
}
}
//退出时,i等于j。将x填到这个坑中。
s[i] = x;
return i;
}
再写分治法的代码:1
2
3
4
5
6
7
8
9void quick_sort1(int s[], int l, int r)
{
if (l < r)
{
int i = AdjustArray(s, l, r);//先成挖坑填数法调整s[]
quick_sort1(s, l, i - 1); // 递归调用
quick_sort1(s, i + 1, r);
}
}
这样的代码显然不够简洁,对其组合整理下:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23void quick_sort(int s[], int l, int r)
{
if (l < r)
{
//Swap(s[l], s[(l + r) / 2]); //将中间的这个数和第一个数交换(以数组中间的数作为基准值!!)
int i = l, j = r, x = s[l];
while (i < j)
{
while(i < j && s[j] >= x) // 从右向左找第一个小于x的数
j--;
if(i < j)
s[i++] = s[j];
while(i < j && s[i] < x) // 从左向右找第一个大于等于x的数
i++;
if(i < j)
s[j--] = s[i];
}
s[i] = x;
quick_sort(s, l, i - 1); // 递归调用
quick_sort(s, i + 1, r);
}
}
快速排序还有很多改进版本,如随机选择基准数,区间内数据较少时直接用另的方法排序以减小递归深度。
注1,有的书上是以中间的数作为基准数的,要实现这个方便非常方便,直接将中间的数和第一个数进行交换就可以了。
1 | var generateTestData = require('https://21cm.js.org/lib/TestDataGenerator'); |
1 | var generateTestData = require('https://21cm.js.org/lib/TestDataGenerator'); |
1 | 归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。 |
首先考虑下如何将将二个有序数列合并。这个非常简单,只要从比较二个数列的第一个数,谁小就先取谁,
取了后就在对应数列中删除这个数。然后再进行比较,如果有数列为空,那直接将另一个数列的数据依次取出即可。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19//将有序数组a[]和b[]合并到c[]中
void MemeryArray(int a[], int n, int b[], int m, int c[])
{
int i, j, k;
i = j = k = 0;
while (i < n && j < m)
{
if (a[i] < b[j])
c[k++] = a[i++];
else
c[k++] = b[j++];
}
while (i < n)
c[k++] = a[i++];
while (j < m)
c[k++] = b[j++];
}
可以看出合并有序数列的效率是比较高的,可以达到O(n)。
1 | 解决了上面的合并有序数列问题,再来看归并排序,其的基本思路就是将数组分成二组A,B,如果这二组组内的数据都是有序的, |
1 | //将有二个有序数列a[first...mid]和a[mid...last]合并。 |
1 | 归并排序的效率是比较高的,设数列长为N,将数列分开成小数列一共要logN步,每步都是一个合并有序数列的过程, |
Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]或者Key[i]>=Key[2i+1]&&key>=key[2i+2]
Key[i]>=Key[2i+1]&&key>=key[2i+2]
称为大顶堆,Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]
称为小顶堆。R[1]
与最后一个元素R[n]
交换,此时得到新的无序区(R1,R2,......Rn-1)
和新的有序区(Rn)
,R[1,2...n-1]<=R[n]
;(R1,R2,......Rn-1)
调整为新堆,R[1]
与无序区最后一个元素交换,得到新的无序区(R1,R2....Rn-2)
和新的有序区(Rn-1,Rn)
。n-1
,则整个排序过程完成。R[1..n]
构造为堆;R[1]
同该区间的最后一个记录交换,然后将新的无序区调整为新的堆。1 | var generateTestData = require('https://21cm.js.org/lib/TestDataGenerator'); |
/*方法说明:堆排序1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23function heapSort(array) {
//建堆
var heapSize = array.length, temp;
for (var i = Math.floor(heapSize / 2); i >= 0; i--) {
adjustHeap(array, i, heapSize);
}
//堆排序
for (var j = heapSize - 1; j >= 1; j--) {
temp = array[0];
array[0] = array[j];
array[j] = temp;
adjustHeap(array, 0, --heapSize);
}
return array;
}
var data = generateTestData(20000);
// console.log(data);
var start = new Date().getTime();
console.log('start sorting....');
var result = heapSort(data);
var end = new Date().getTime();
console.log('耗时: ' + (end - start) + ' ms');
// console.log(result);
1 | var arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 23, 45, 55, 44, 22, 33]; |
1 | var arr = []; |
1 | function fibonacci(n) { |
1 | for (var index in myArray) { // 千万别这样做 |
这绝对是一个糟糕的选择,为什么呢?
简而言之,for-in是为普通对象设计的,你可以遍历得到字符串类型的键,因此不适用于数组遍历。
tag:
缺失模块。
1、请确保node版本大于6.2
2、在博客根目录(注意不是yilia根目录)执行以下命令:
npm i hexo-generator-json-content --save
3、在根目录_config.yml里添加配置:
jsonContent: meta: false pages: false posts: title: true date: true path: true text: false raw: false content: false slug: false updated: false comments: false link: false permalink: false excerpt: false categories: false tags: true