先展示一下動(dòng)畫效果：
首先先簡(jiǎn)單了解一下什么是直接插入排序：
直接插入排序會(huì)在遍歷的過程中將一個(gè)序列分為兩部分，前半部分是已經(jīng)排好了的有序序列，后半部分是還未排序的無序序列。在無序序列中從左往右遍歷，每一步將一個(gè)待排序的元素，按其排序碼的大小，插入到前面已經(jīng)排好序的一組元素的適當(dāng)位置上去，直到元素全部插入為止。
那基本概念已經(jīng)了解了，現(xiàn)在就用代碼將這樣一個(gè)排序的過程展示出來：
1、既然要畫畫，那我們就需要一塊畫布：
<canvas id="canvas"></canvas>
并且對(duì)即將繪制的圖形進(jìn)行一些設(shè)置：
const WIDTH = 500,HEIGHT = 300//畫布的寬高
const COLUMN_WIDTH = 15,COLUMN_MARGIN = 1//條形圖的一個(gè)豎條的寬以及兩個(gè)豎條之間的間隔
const LENGTH = Math.floor(WIDTH / (COLUMN_WIDTH + COLUMN_MARGIN))//根據(jù)畫布的大小、豎條的寬以及兩個(gè)豎條之間的距離計(jì)算出一個(gè)畫布可以容納的豎條
const canvas = document.getElementById('canvas')//獲取畫布
const ctx = canvas.getContext('2d')//創(chuàng)建畫筆
let sortArray = new Array()//存儲(chǔ)需要排序的序列
let animationTime = 3
canvas.height = HEIGHT
canvas.width = WIDTH
2、準(zhǔn)備工作做好了，那我們就需要有一個(gè)需要排序的序列，這里就用隨機(jī)數(shù)的方式創(chuàng)建一個(gè)無序數(shù)組：
function init(){
for(let i = 0; i < LENGTH; i++){
sortArray[i] = Math.floor(Math.random() * HEIGHT + 1)
}
}
3、將這個(gè)無序序列的每一項(xiàng)變成條形：
function drawColumn(ctx, index, height, color){//畫筆、當(dāng)前當(dāng)前遍歷的元素的索引、該元素的高度、顏色
ctx.fillStyle = color
let x = index * (COLUMN_MARGIN + COLUMN_WIDTH)
let y = HEIGHT
ctx.fillRect(x,y,COLUMN_WIDTH,-height)//左上角的x坐標(biāo)，左上角的y坐標(biāo)，元素的寬度，元素的高度
}
4、將變成條形的序列渲染出來：
function render(ctx){
for(let i = 0; i < sortArray.length; i++){
drawColumn(ctx,i,sortArray[i],'black')
}
}
調(diào)用render(ctx),之后我們打開瀏覽器就可以看到這個(gè)無序序列就已經(jīng)展示在頁面上啦,如下圖所示：
5、我們可以發(fā)現(xiàn)這個(gè)序列雖然展示出來了，但還是無序的。接下來就用直接插入排序的方式給他排個(gè)序：
function sort(ctx){
let item//哨兵，用來保存要交換位置的其中一個(gè)元素，這樣交換的時(shí)候就不會(huì)有將上一個(gè)元素覆蓋之后丟失的情況了
for(let i = 0; i < LENGTH; i++){
for(let j = i + 1; j > 0; j--){
if(sortArray[j-1] > sortArray[j]){
item = sortArray[j-1]
sortArray[j-1] = sortArray[j]
sortArray[j] = item
}else{
break
}
}
}
}
排完序后，可以看到序列已經(jīng)從小到的排好序了：
6、接下來就要讓它從無序變?yōu)橛行虻倪@個(gè)過程以動(dòng)畫的形式展示出來。所以在sort函數(shù)中，每當(dāng)當(dāng)前索引改變的時(shí)候都需要更新一下視圖。這里需要對(duì)sort函數(shù)進(jìn)行改造：
function sort(ctx){
let item
for(let i = 0; i < LENGTH; i++){
for(let j = i + 1; j > 0; j--){
if(sortArray[j-1] > sortArray[j]){
updateView(ctx, copyArray(sortArray), i, j - 1, j)//當(dāng)交換位置的時(shí)候更新視圖
item = sortArray[j-1]
sortArray[j-1] = sortArray[j]
sortArray[j] = item
}else{
break
}
updateView(ctx, copyArray(sortArray), i, j - 1, j)//當(dāng)索引跳到下一個(gè)未排序的元素時(shí)更新視圖
}
updateView(ctx, copyArray(sortArray), i, -1, -1)//當(dāng)當(dāng)前索引改變時(shí)更新視圖
}
}
每當(dāng)原數(shù)組發(fā)生改變，就將它復(fù)制一份,傳入updateView中更新視圖：
function copyArray(arr){
let newArr = new Array()
for(let i = 0; i < arr.length; i++){
newArr[i] = arr[i]
}
return newArr
}
update函數(shù)中有一個(gè)定時(shí)器，每隔一定的時(shí)間就會(huì)重新渲染一次：
function updateView(ctx, arr, currentIndex, compareIndex1, compareIndex2){
setTimeout(() => {
render(ctx, arr, currentIndex, compareIndex1, compareIndex2)
},animationTime++*20)
}
7、為了能讓整個(gè)過程更加清晰，這里在渲染的時(shí)候會(huì)將已排序的元素用綠色表示出來，未排序的元素用黑色表示，當(dāng)前正在比較的元素左側(cè)的用橙色表示，右側(cè)的用綠色表示，這里需要改造一下render函數(shù)：
function render(ctx, arr, currentIndex, compareIndex1, compareIndex2){
ctx.clearRect(0,0,WIDTH,HEIGHT)
for(let i = 0; i < arr.length; i++){
if(i == compareIndex1){
drawColumn(ctx,i,arr[i],'orange')
}else if(i == compareIndex2){
drawColumn(ctx,i,arr[i],'blue')
}else if(i < currentIndex){
drawColumn(ctx,i,arr[i],'green')
}else{
if(currentIndex == arr.length - 1){
drawColumn(ctx,i,arr[i],'green')
}else{
drawColumn(ctx,i,arr[i],'black')
}
}
}
}
到這里就結(jié)束啦，運(yùn)行render函數(shù)就可以看到動(dòng)態(tài)的排序過程。
