자바스크립트 구현 및 정렬 알고리즘 설명(99js 노트)

버블정렬

버블링의 원리는 가장 큰 요소 또는 가장 작은 요소를 "떠다니는" 것입니다

삽입정렬, 선택정렬, 퀵정렬, 버블정렬은 모두 비교정렬입니다

생각

소수점을 앞에, 큰 숫자를 뒤에 두어 인접한 두 숫자를 순서대로 비교합니다.

1단계: 첫 번째와 두 번째 숫자를 비교하고 소수점 앞에 숫자를 넣고 뒤에 큰 숫자를 넣습니다. 두 번째 숫자와 세 번째 숫자를 비교하려면 소수점을 앞에, 큰 숫자를 뒤에 넣고 마지막 두 숫자를 비교할 때까지 계속해서 소수점을 앞에 놓고 큰 숫자를 뒤에 넣습니다.
2 단계: 두 번째 패스에서: 여전히 첫 번째 숫자 쌍에서 비교를 시작합니다(두 번째 숫자와 세 번째 숫자의 교환으로 인해 첫 번째 숫자가 더 이상 두 번째 숫자보다 작지 않기 때문일 수 있음). 소수점 먼저, 큰 숫자가 배치된 후 두 번째에서 마지막 숫자까지 비교가 계속됩니다(첫 번째에서 마지막 위치가 이미 가장 큰 위치임). 두 번째 패스가 끝나면 두 번째에서 마지막 숫자까지 새로운 최대 숫자가 얻어집니다. 마지막 위치(실제로 전체 시퀀스에서 두 번째로 큰 숫자입니다).
이렇게 계속해서 정렬이 최종적으로 완료될 때까지 위의 과정을 반복하세요.
정렬 과정에서는 항상 작은 숫자가 앞쪽에 배치되고 큰 숫자가 뒤쪽에 배치되는데, 이는 거품이 떠오르는 것과 동일하므로 이를 버블 정렬이라고 합니다.
버블 정렬 애니메이션 효과

구현: 이 코드는 비교적 간단하며 알고리즘에서 가장 기본적이고 기본적인 코드입니다. . .
주의할 점 3가지

1. 클래스를 교환하는 방법은 자바스크립트에서 a=[b,b=a][0]을 사용하면 해결되는데, 이는 매우 영리한 방법입니다.
교체

코드 복사 코드는 다음과 같습니다.

var,a,b,temp

온도 = a;

a=b;

b = 온도

교환방법
2. 루프 변수의 캐시에 주의하세요. Array.length
가 여기에 캐시됩니다. 3. 첫 번째 숫자부터 마지막 숫자부터 n번째 숫자까지 비교하는 임베디드 루프에 주목하세요. n은 비교 단계 수입니다

function bubbleSort(array) {
var l=array.length;
for (var i = 0; i < l; i++) {//比较的step数为数组的长度
for (var j = 0; j < l-i; j++) {//内嵌交换的次数是从第一个数比较到倒数第总长-n个数，n则为比较的step数
if (array[j] < array[j - 1]) {
array[j] = [array[j - 1], array[j - 1] = array[j]][0]//在这里交换元素
}
}
for (var k = 0; k < l; k++) {
console.log(array[k] + ",");
}
console.log('这是第'+(i+1)+'次排序')
}
}
var a = [6,54,6,22,5,7,8,2,34];
bubbleSort(a);

로그인 후 복사

애니메이션 효과

삽입정렬
매우 간단합니다. 카드를 뽑고 넣는 단계만 거치면 됩니다!
아이디어:

1 먼저 카드를 뽑고 현재 손에 있는 모든 카드가 비어 있음 = []으로 설정되어 푸시(arr[0])를 뽑는다고 가정합니다.
2 다음 카드를 꺼내서 a로 설정하고 모든 빈 카드(이미 정렬됨)를 뒤에서 앞으로 스캔합니다.
3. 손에 있는 빈[empty.length-n](정렬된) 카드가 새 요소보다 크면 카드를 다음 위치로 이동합니다(공간 확보). 길이-n 1]
4 정렬된 카드 비어 있음[empty.length-n]이 a
보다 작거나 같을 때까지 3단계를 반복합니다. 5empty[empty.length-n]=a
위치에 a를 삽입한다 62단계를 반복하세요
다만 아직 자바스크립트 코드를 구현하기는 조금 어렵습니다.

function insert(arr) {
var l = arr.length;
var empty = [];//空数组，表示我们的手
empty.push(arr[0]);//我们先摸起来一张
for (var i = 1; i < l; i++) {//注意这里起点是1，因为我们已经摸了一张了！
if (arr[i] > empty[empty.length - 1]) {
empty[empty.length] = arr[i]
} //如果比有序数组empty还大，直接放到末尾
for (var j = empty.length; j > 0 && arr[i] < empty[j - 1]; j--) { //从最大值跟arr进行比较，为了给arr腾空。当arr<有序数组的某一位时，就不用移动了。
empty[j] = empty[j - 1]; //向右移动
empty[j - 1] = arr[i]; //把值放到空出来的位置上
}
//console.log(empty)
}
return empty
}

로그인 후 복사

여기서 더 중요한 지식 포인트는 'and'를 의미하는 && 기호입니다. 즉, 표현이 참이 되려면 양쪽의 조건이 모두 충족되어야 합니다.
&& 기호는 예를 들어 if(a){fun()}이 a&&b
와 같은 경우에도 대체될 수 있습니다. 또 다른 매우 중요한 포인트
배열이 arr이고 "마지막 항목"이 arr[arr.length-1]이라고 가정합니다.

애니메이션 정렬

선택 정렬
또한 간단한 정렬 알고리즘이기도 합니다.

사물:

가장 작은 요소를 찾아서 배열에 넣은 다음, 다음으로 가장 작은 요소를 찾아서 배열에 넣는 식으로 진행됩니다.
먼저, 정렬되지 않은 배열에서 가장 작은 요소를 찾는 방법은 연속적인 판단과 할당을 통해 이루어질 수 있습니다. 즉, 배열의 첫 번째 요소인 array[0]이 가장 작은 요소라고 가정하고 그 다음에는 해당 배열의 일련 번호를 사용합니다. 배열의 "가장 작은 요소"는 0입니다
그런 다음 배열을 탐색합니다. 배열의 두 번째 요소가 그보다 작으면 두 번째 요소가 가장 작은 요소라는 의미이며 "0"을 "1"로 업데이트합니다.
순회가 완료되면 이 시리즈의 최소 요소 첨자가 "n"임을 알 수 있습니다. 이를 직접 꺼내서 정렬된 시퀀스(배열[n])의 시작 위치에 저장합니다
그런 다음, 정렬되지 않은 나머지 요소 중에서 가장 작은 요소를 계속 찾아 정렬된 시퀀스의 끝에 넣습니다. 이때 순회하는 첨자는 1부터 시작한다는 점에 유의하세요. 왜냐하면 우리는 이미 최소한의 요소를 선택했기 때문입니다.
모든 요소가 정렬될 때까지 계속됩니다.

function selectSort(array) {
var min;
var l = array.length;//缓存长度
for (var i = 0; i < l; i++) {//开始进行循环，一共循环l次，就可以找出l个元素了
min = i;//假设第一个为最小元素
for (var j = i + 1; j < l; j++) {//从第一个开始循环，遍历
if (array[min] > array[j])//判断之后的是否比前面的小
min = j;//更新“最小”的下标
}
if (min != i) {//这里因为是在同一个数组内进行操作，所以直接交换元素即可。比如数组第一项是i，那么我找出了最小元素为array[min],那么我就需要把这个min跟i交换。以此类推。
array[i]= [array[min],array[min]=array[i]][0];//交换元素
}
}
return array;
}

로그인 후 복사

这里仍然注意的是交换的写法 array[i]= [array[min],array[min]=array[i]][0]
可以方便的把array[i]与array[min]交换~

排序动画

快速排序

快速排序是目前最强大的排序算法，算法利用了递归的思想。

思路

从数组中挑出一个元素，称为 “基准”，这个可以直接利用length/2挑出来
遍历数组，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。通俗来讲：男的站左边，女的站右边。。
之后我们得到了一个这样的数组 array= 比基准小的部分组成的数组lArray+基准+比基准大的部分组成的数组rArray。
那么我们之后只需要再把lArray,rArray进行“同样的”处理即可~
这就需要用到递归的写法了。处理之后，lArray又分成了 lArray的基准，比lArray基准还小的，比lArray基准还大的。。
那么我们不断的进行操作，男的站左边，女的站右边。。
直到我们发现，lArray的长度变成1了，不足以再分下去了，我们认为排序结束。

function quickSort(arr) {
var l = arr.length;//缓存数组长度
if(arr.length <= 1){return arr}; //如果我们拿到的lArray,rArray长度比1都小，那就不用排了~
var num = Math.floor(arr.length / 2);//取数组中间的那个数。注意length/2不一定是整数，用Math.floor取整
var numValue = arr.splice(num, 1)[0];//利用splice方法，取一个元素出来，注意语法
var left = [];//创建左边基准容器
var right = [];//创建右边基准容器
for (var i = 0; i < l; i += 1) {//开始遍历数组
arr[i] < numValue &#63; left.push(arr[i]) : right.push(arr[i]);//男的站左边，女的站右边。。
}
return quickSort(left).concat([numValue], quickSort(right))//递归，继续对左右数组进行操作。
}

로그인 후 복사

动画效果：

这里注意 arr.splice(num,1)虽然只抽了一个数，但splice的结果也是数组，需要[0],要不然结果就会很奇葩的出现一堆array(1)的数组了。。。
splice的参考：http://www.jb51.net/w3school/js/jsref_splice.htm
Math.floor即Math对象的参考http://www.jb51.net/w3school/js/js_obj_math.htm
递归是什么：http://baike.baidu.com/view/96473.htm

以上四个算法除了快速排序，都是简单排序算法，而这四个算法在面试中考的都非常频繁~
在这里仍然要强调一点，以上的算法大量使用了循环及数组的相关知识，一定要背熟！