排序演算法動畫演示

① 用Javascript寫排序演算法的動畫演示

1.讓JavaScript暫停下來，慢下來。
JavaScript排序是很快的，要我們肉眼能看到它的實現過程，我首先想到的是讓排序慢下來。 排序的每一個循環都讓它停300ms然後再繼續進行。 怎麼樣才能停下來呢。查了一下JavaScript貌似沒有sleep()這樣的函數。暫停做不到，但是可以想辦法讓實現跟暫停差不多的效果。比如在循環里做一些無關的事情 。
首先嘗試了讓while(true)來一直執行一個空操作。執行一段時間再回到排序邏輯。代碼大致是這樣：
for (var i = 0; i < 3; i++) {
document.writeln(i); //DOM操作
var now = new Date().getTime();
while(new Date().getTime() - now < 3000){}
}

慢是慢下來了。不過太耗資源，排序進行過程中dom並不會有任何改變，直到排序結束， DOM會變成排序好之後的樣子。 但是如果設置斷點一步步執行的時候 又可以看到一步步的排序變化。估計是因為這個操作太耗資源導致瀏覽器下達了一個DOM操作的命令但是一直騰不出資源來進行DOM操作。所以真正DOM操作的時候在js代碼執行結束之後。
所以讓JavaScript排序慢來來還是沒有實現。
另一種讓JavaScript暫停下來的思路：
寫這個文章的時候又想到一種方法來讓JavaScript停下來。 那就是AJAX的同步請求，以及超時操作。 也就是在要停下來的地方放一個AJAX請求，同步請求， 然後設置超時。超時的時間就是我們要暫停的時間。為了避免在到達超時請求之前服務 器就返回了我們的AJAX請求。可以在服務端運行類似 sleep()的程序 。從而保證AJAX不會返回。直接超時然後返回到我們的循環。不過這只是個設想。有興趣的可以去嘗試一下。
2.閉包和定時器。 這種思路不需要讓排序過程慢下來。而是使用閉包緩存排序過程中數組的變化。然後使用setTimeout來確定展示每一個數組狀態的順序。在排序循環中放入類似下面的代碼。
(function(){
var theArr = arr.slice();//當前數組狀態的備份
setTimeout(function(){
bubbleSortDom(theArr);//排序的DOM操作。
},500*timeCount);
timeCount++;//定時器的順序。
})();

不過後來發現這樣子寫的話代碼量會比較大，邏輯有修改的話要修改的地方會有點多。局限性很多，比如要實現排序動畫加快或減慢操作幾乎是很困難的。所以還要另想辦法。
3.緩存排序中的數組狀態。
也就是在排序過程中。將數組的每一輪循環的狀態保存到一個數組。然後再用這個數組依次將排序狀態保存下來。 只需要在排序中加入一句就行。
this.pushHis(arr.slice(),i-1,j,k,temp);

這樣就只需要一個setInterval()就可以了。並且可以很方便的實現動畫的加快與減慢。邏輯也比較好理解 。
問題二：如何實現JavaScript排序動畫的加快與減慢。
我們問題一使用的第三種方法。 得到一個保存了每一步排序狀態的數組arr。 然後我們可以使用一個setInterval()定時器一步步展現排序狀態。 如果要加快速度或減慢速度。就clearInterval()，修改定時器的執行間隔，重新setInterval()，從前一個定時器執行到數組中的位置開始執行。
問題三：對於使用遞歸實現的數組怎麼辦？ 不是在原數組上進行操作的怎麼辦？
使用遞歸實現的排序。 可能並沒有在一個數組上進行操作，只是最後返回一個排序好的數組出來。那麼我們要如何獲得排序中的數組的完整狀態呢。
比如快速排序。
最開始不考慮動畫，我的實現是這樣的：
function quickSort(arr){
var len = arr.length,leftArr=[],rightArr=[],tag;
if(len<2){
return arr;
}
tag = arr[0];
for(i=1;i<len;i++){
if(arr[i]<=tag){
leftArr.push(arr[i])
}else{
rightArr.push(arr[i]);
}
}
return quickSort(leftArr).concat(tag,quickSort(rightArr));
}

然後為了考慮動畫，我改寫了它的邏輯，讓它在同一個數組上進行了實現。 其實是在遞歸的時候傳入了當前的的子數組在原數組中的起始位置。從而在原數組上進行了操作。
用了兩種方法來實現方式。在排序邏輯上略有不同。
第一種是先跟遠處的對比。遇到比自己小的放到自己前面去。循環序號+1。比自己大的放到當前排序子數組的最後面去，循環序號不變。直到排列完成。
這種方法的缺點是即使是一個有序數組。它也會重新排。
第二種方法是 除了標記位，再設置一個對比位。 遇到比自己小的，放到前面去，標記位的位置+1，標記位與對比位之間所有的往後面移動一個位置。
遇到比自己大的。標記位不變，對比位+1。
這種方法的缺點是對數組進行的操作太多。優點是對有序數組不會再排。
方式一：
function quickSort(arr,a,b,qArr){

var len = arr.length,leftArr=[],rightArr=[],tag,i,k,len_l,len_r,lb,ra,temp;
if(a == undefined && b == undefined){
a = 0; b= arr.length-1;//初始化起始位置。
}
if(qArr == undefined){
qArr = arr.slice();
}

if((len == 2 && arr[0] == arr[1])||len<2){
return arr;
}

tag = qArr[a];
for (i = 1; i < len;) {
if(qArr[a+i]<=tag){
leftArr.push(qArr[a+i]);
qArr[a+i-1] = qArr[a+i];
qArr[a+i] = tag;
k = a+i;
i++;
}else{
if(leftArr.length+rightArr.length == len-1){
break;
}
temp = qArr[a+i];
qArr[a+i] = qArr[b-rightArr.length];
qArr[b-rightArr.length] = temp;
rightArr.push(temp);
k = a+i-1;
}
this.pushHis(qArr.slice(),a,b,k);
}

len_l = leftArr.length;
len_r = rightArr.length;
if(len_l== 0){
lb = a;
}else{
lb = a+len_l -1;
this.sort(leftArr,a,lb,qArr);
}

if(len_r == 0){
ra = b;
}else{
ra = b + 1 - len_r;
this.sort(rightArr,ra,b,qArr)
}
return qArr
}

方式二：
function quickSort2(arr,a,b,qArr){
var len = arr.length,leftArr=[],rightArr=[],tag,i,j,k,temp,len_l,len_r,lb,ra;
if(a == undefined && b == undefined){
a = 0; b= arr.length-1;//初始化起始位置。
}
if(qArr == undefined){
qArr = arr.slice();
}
if(len<2){
return arr;
}
if(len == 2 && arr[0] == arr[1]){
return arr;
}
tag = qArr[a];
for (i = 1,k = 0; i < len;) {
if(qArr[a+i]>=tag){
rightArr.push(qArr[a+i]);
i++;
}else{
temp = qArr[a+i];
for(j = a+i;j>a+k;j--){
qArr[j] = qArr[j-1];
// this.pushHis(qArr.slice(),a,b,a+k);
}
qArr[a+k] = temp;
leftArr.push(temp);
k++;
i++;
}
this.pushHis(qArr.slice(),a,b,a+k,i-1);
}
len_l = leftArr.length;
len_r = rightArr.length;
if(len_l== 0){
lb = a;
}else{
lb = a+len_l -1;
this.sort(leftArr,a,lb,qArr);
}
if(len_r == 0){
ra = b;
}else{
ra = b + 1 - len_r;
this.sort(rightArr,ra,b,qArr)
}
return qArr;
}

具體的不同下面會有動畫演示。
問題四：動畫的流暢。
排序動畫的DOM操作是很多的很快的。這里我做的優化只是讓每一個排序步驟只涉及一個DOM操作。 全部由JavaScript拼接好，一次替換。類似下面的代碼。
效果圖：

主要實現了：
冒泡排序JavaScript動畫演示
插入排序JavaScript動畫演示
選擇排序JavaScript動畫演示
快速排序JavaScript動畫演示
歸並排序JavaScript動畫演示
希爾排序JavaScript動畫演示

② 冒泡排序演算法 [「排序演算法設計」教學設計]

一、教材依據本節課是奧教版《演算法與程序設計》(選修1)第四章《演算法與程序實現》的第4節第1課時。二、設計思想【教學指導思想】：基於問題主導的教學模式。
【設計理念】：本節課採用基於問題主導的創新教學模式，指導學生在問題解決視野下去親歷演算法分析與程序設計實踐、理解演算法思想、發現新問題，從而全面提升學生的能力。
【教材分析】：排序演算法是程序設計的基本演算法，主要要求學生理解選擇排序演算法，選擇排序演算法的特點，進一步分析排序演算法時間和空間效率。
【學情分析】：高二年級的學生在高一階段襪畝山的必修教材中已經學習了編製程序解決問題，他們已經具有較強的邏輯思維能力和分析問題的能力，只要講清楚演算法，本節課的內容對學生來說應該容易掌握。
三、教學目標
【知識目標】：理解選擇排序演算法思想，學會使用選擇排序演算法思想解決問題。
【能力目標】：通過學習選擇排序演算法，提高學生分析與解決問題的能力。
【情感態度與價值觀】：通過上機完成「大型國際運動會上的國家排序問題"VB程序設計，體驗編程快樂、感受成功的喜悅與程序的魅力。
四、教學重點
選擇排序演算法的基本思想及相關的程序實現。
五、教學難點
如何使用選擇排序演算法解決實際的問題。
六、教學准備
1.用PowerPoint 2003製作的課件。
2.從網上下載選擇排序的動畫演示文件。
七、教學過程
1.引入新課：(以一些現實生活的實際問題開始，啟發同學們去思考)
教師：同學們每次的考試成績我們會以Excel表格的形式公布給大家，同學們想想計算機是如何在瞬間進行分數排序的呢?
學生想。
2.啟發思考，分析選擇排序演算法及程序實現。
教師：好，今天我們就來學習選擇排序演算法。
開始新課學習：
教師：現在我們一起看看人工是如何進行數據的排序的，老師給出8位同學的分數，同學們把它們由小到大地排成順序。數據分別是：86.5，77.5，87，68.9，89.6，77.2，79.7，71.1。同學們想想笫一個位置應該放哪個數?
學生：放最小的。
教師：好，那麼，我們是不是只需要將最小的數68.9與在第一個位置的數86.5進行交換呢?
學生：是。
教師：同學們再想一下第二個位置是不是應該放置的是除了第一個以外的數中最小的呢?
學生：是。
教師：那麼第N-1個位置應該放什麼呢?
學生：應該放置告中的是除了前N-2個以外的數中最小的。
教師：老師是不是可以總結我們剛才的演算法，所謂選擇排序，就是給數組的N-1個位置選擇合適的數據，而每次是選擇第i個位置的數據到最後一個位置(第Ⅳ個位置)的數據的最小值，然後將找到的最小數據與第i個位置上的數據交換?
學生：是的。
教師：下面我用一個動畫演示剛才的演算法，請同學們看大屏幕。
現在我們只需要將剛才的演算法用VB語言表達出來，就是選擇排序的程序，那麼我們需要解決三個問題：
(1)給數組的N-1個位置選擇合適的數據?這個問題顯然我們可以用一個循環結構來完成：For i=l【o
N-1Next i
(2)如何尋找第i個位置的數據到最後一個位置(第Ⅳ個位置)的數據的最小值?
這個問題也就是在數組中的極值(最大值或最小值)的問題。其實我們只關心最小值數據的位置，用變數M記錄其位置。
於是我們很容易寫出選擇排序的程序。
3.調試程序：
教師：同學們想不想看一下運行結果呢?
學生：想(很耐橘強烈)。
教師：運行程序後，輸入測試數據，可得排序後的輸出結果在窗體上。
4.課堂實踐練習與知識拓寬：
(1)完成課本127頁的國家名排序問題。
【設計意圖】：使學生看到選擇排序不僅可以對數字排序，也可以對字元串排序，同時也能達到對選擇排序的應用練習。
(2)明明的隨機數(題目描述發送到學生機的桌面)
【設計意圖】：這個問題是很現實的例子，學生對這個問題很感興趣，激發他們探索的慾望，要求學習優秀的學生必須完成，我想通過這個問題，一方面提升學生學習的積極性；另一方面再通過這個實際問題的解決，實現本節課的知識目標。
【學習評價】：教師隨機讓個別學生講解練習題的演算法、演示其所編程序，師生共同進行點評。
【課堂小結】：
(1)什麼是選擇排序演算法?
(2)選擇排序演算法的實質及時間和空間效率。
(3)選擇排序演算法的優點、缺點。
八、教學反思
通過本節課的 教學設計 ，我認識到信息技術教學的關鍵是要調動學生的積極性，演算法與程序設計這部分知識如果課堂教學設計不當，就會讓學生覺得很枯燥，所以我將抽象的問題通俗化，復雜的問題分解成幾個小問題來解決，這樣學生就很容易接受，再加上所舉的例子都是學生身邊的實際事例，使學生很想知道問題的答案，從而極大地調動了學生的積極性。
(作者單位陝西省成陽市禮泉縣第一中學)

③ 希爾排序法原理

希爾排序法(縮小增量法) 屬於插入類排序，是將整個無序列分割成若干小的子序列分別進行插入排序的方法。
演算法思想簡單描述
在直接插入排序演算法中，每次插入一個數，使有序序列只增加1個節點，
並且對插入下一個數沒有提供任何幫助。如果比較相隔較遠距離（稱為
增量）的數，使得數移動時能跨過多個元素，則進行一次比較就可能消除
多個元素交換。D.L.shell於1959年在以他名字命名的排序演算法中實現
了這一思想。演算法先將要排序的一組數按某個增量d分成若干組，每組中
記錄的下標相差d.對每組中全部元素進行排序，然後再用一個較小的增量
對它進行，在每組中再進行排序。當增量減到1時，整個要排序的數被分成
一組，排序完成。
下面的函數是一個希爾排序演算法的一個實現，初次取序列的一半為增量，
以後每次減半，直到增量為1。
希爾排序是不穩定的。

④ 面試必會八大排序演算法（Python）

一、插入排序

介紹

插入排序的基本操作就是將一個數據插入到已經排好序的有序數據中，從而得到一個新的、個數加一的有序數據。

演算法適用於少量數據的排序，時間復雜度為O(n^2)。

插入排演算法是穩定的排序方法。

步驟

①從第一個元素開始，該元素可以認為已經被排序

②取出下一個元素，在已經排序的元素序列中從後向前掃描

③如果該元素（已排序）大於新元素，將該元素移到下一位置

④重復步驟3，直到找到已排序的元素小於或者等於新元素的位置

⑤將新元素插入到該位置中

⑥重復步驟2

排序演示

演算法實現

二、冒泡排序

介紹

冒泡排序（Bubble Sort）是一種簡單的排序演算法，時間復雜度為O(n^2)。

它重復地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重復地進行直到沒有再需要交換，也就是說該數列已經排序完成。

這個演算法的名字由來是因為越小的元素會經由交換慢慢「浮」到數列的頂端。

原理

循環遍歷列表，每次循環找出循環最大的元素排在後面；

需要使用嵌套循環實現：外層循環控制總循環次數，內層循環負責每輪的循環比較。

步驟

①比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。

②對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對。在這一點，最後的元素應該會是最大的數。

③針對所有的元素重復以上的步驟，除了最後一個。

④持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較。

演算法實現：

三、快速排序

介紹

快速排序（Quicksort）是對冒泡排序的一種改進，借用了分治的思想，由C. A. R. Hoare在1962年提出。

基本思想

快速排序的基本思想是：挖坑填數 + 分治法。

首先選出一個軸值(pivot，也有叫基準的)，通過一趟排序將待排記錄分隔成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分的關鍵字小，則可分別對這兩部分記錄繼續進行排序，以達到整個序列有序。

實現步驟

①從數列中挑出一個元素，稱為 「基準」（pivot）；

②重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的後面（相同的數可以到任一邊）；

③對所有兩個小數列重復第二步，直至各區間只有一個數。

排序演示

演算法實現

四、希爾排序

介紹

希爾排序（Shell Sort）是插入排序的一種，也是縮小增量排序，是直接插入排序演算法的一種更高效的改進版本。希爾排序是非穩定排序演算法，時間復雜度為：O(1.3n)。

希爾排序是基於插入排序的以下兩點性質而提出改進方法的：

·插入排序在對幾乎已經排好序的數據操作時， 效率高， 即可以達到線性排序的效率；

·但插入排序一般來說是低效的， 因為插入排序每次只能將數據移動一位。

基本思想

①希爾排序是把記錄按下標的一定量分組，對每組使用直接插入演算法排序；

②隨著增量逐漸減少，每組包1含的關鍵詞越來越多，當增量減至1時，整個文件恰被分成一組，演算法被終止。

排序演示

演算法實現

五、選擇排序

介紹

選擇排序(Selection sort)是一種簡單直觀的排序演算法，時間復雜度為Ο(n2)。

基本思想

選擇排序的基本思想：比較 + 交換。

第一趟，在待排序記錄r1 ~ r[n]中選出最小的記錄，將它與r1交換；

第二趟，在待排序記錄r2 ~ r[n]中選出最小的記錄，將它與r2交換；

以此類推，第 i 趟，在待排序記錄ri ~ r[n]中選出最小的記錄，將它與r[i]交換,使有序序列不斷增長直到全部排序完畢。

排序演示

選擇排序的示例動畫。紅色表示當前最小值，黃色表示已排序序列，藍色表示當前位置。

演算法實現

六、堆排序

介紹

堆排序（Heapsort）是指利用堆積樹（堆）這種數據結構所設計的一種排序演算法，它是選擇排序的一種。

利用數組的特點快速指定索引的元素。

基本思想

堆分為大根堆和小根堆，是完全二叉樹。

大根堆的要求是每個節點的值不大於其父節點的值，即A[PARENT[i]] >=A[i]。

在數組的非降序排序中，需要使用的就是大根堆，因為根據大根堆的要求可知，最大的值一定在堆頂。

排序演示

演算法實現

七、歸並排序

介紹

歸並排序（Merge sort）是建立在歸並操作上的一種有效的排序演算法。該演算法是採用分治法（Divide and Conquer）的一個非常典型的應用。

基本思想

歸並排序演算法是將兩個（或兩個以上）有序表合並成一個新的有序表，即把待排序序列分為若干個子序列，每個子序列是有序的。然後再把有序子序列合並為整體有序序列。

演算法思想

自上而下遞歸法（假如序列共有n個元素）

① 將序列每相鄰兩個數字進行歸並操作，形成 floor(n/2)個序列，排序後每個序列包含兩個元素；

② 將上述序列再次歸並，形成 floor(n/4)個序列，每個序列包含四個元素；

③ 重復步驟②，直到所有元素排序完畢。

自下而上迭代法

① 申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合並後的序列；

② 設定兩個指針，最初位置分別為兩個已經排序序列的起始位置；

③ 比較兩個指針所指向的元素，選擇相對小的元素放入到合並空間，並移動指針到下一位置；

④ 重復步驟③直到某一指針達到序列尾；

⑤ 將另一序列剩下的所有元素直接復制到合並序列尾。

排序演示

演算法實現

八、基數排序

介紹

基數排序（Radix Sort）屬於「分配式排序」，又稱為「桶子法」。

基數排序法是屬於穩定性的排序，其時間復雜度為O (nlog(r)m) ，其中 r 為採取的基數，而m為堆數。

在某些時候，基數排序法的效率高於其他的穩定性排序法。

基本思想

將所有待比較數值（正整數）統一為同樣的數位長度，數位較短的數前面補零。然後，從最低位開始，依次進行一次排序。這樣從最低位排序一直到最高位排序完成以後，數列就變成一個有序序列。

基數排序按照優先從高位或低位來排序有兩種實現方案：

MSD（Most significant digital） 從最左側高位開始進行排序。先按k1排序分組, 同一組中記錄, 關鍵碼k1相等,再對各組按k2排序分成子組, 之後, 對後面的關鍵碼繼續這樣的排序分組, 直到按最次位關鍵碼kd對各子組排序後. 再將各組連接起來,便得到一個有序序列。MSD方式適用於位數多的序列。

LSD （Least significant digital）從最右側低位開始進行排序。先從kd開始排序，再對kd-1進行排序，依次重復，直到對k1排序後便得到一個有序序列。LSD方式適用於位數少的序列。

排序效果

演算法實現

九、總結

各種排序的穩定性、時間復雜度、空間復雜度的總結：

平方階O(n²)排序：各類簡單排序：直接插入、直接選擇和冒泡排序；

從時間復雜度來說：

線性對數階O(nlog₂n)排序：快速排序、堆排序和歸並排序；

O(n1+§))排序，§是介於0和1之間的常數：希爾排序 ；

線性階O(n)排序：基數排序，此外還有桶、箱排序。

⑤ 用VB編制一個動態的演示排序操作的實用程序

現在VB的話一般用ADO連接數據的比較多，可以用控制項ADODC直接生成連接數據的語句，最好把最後連接的機器的名稱改成IP。
1.在資料庫中建立HM和HM2兩個表，注意你建立數據表的時候各列名稱設定好。
2.VB中觸發時間是List1的CLICK時間，然後檢測是否收到ASC碼13（即回車符）檢測到後往下執行
3.對輸入的字元串做檢測，可以先檢測長度是否7位或11位，然後對各個位是否為數字做檢測（可以循環去ASC的辦法），是則往下執行，否則List1清零。
4.VB連接資料庫，去其中號碼與List1對用的那條記錄，然後去各個列的內容分別填入list2、list3、list4、list5就OK了。

總體而言的話這個程序應該不難，不過我沒用VB連接ACESS所以不能給你全部的代碼，其他的我有部分類似的程序，你要的話發消息給我吧。

⑥ 十大經典排序演算法動畫演示

姓名：鄧霜意                           學號：20021210598

【嵌牛導讀】：排序演算法是演算法學習中的重難點，本文通過動畫的形式清楚明了的展示經典排序演算法的原理槐野與思想。

【嵌牛鼻子】：快速排序 選擇排序 堆排序 希爾排序 歸並排序

【嵌牛提問】：最好的排序演算法是什麼？

【嵌牛正文】：

1、Sorting Algorithms Animations

2、演算法的分碧森類

3、時間復雜度

演算法

1、冒泡排序

2、快速排序

3、直接插入排序

4、選擇排序

5、歸並排序

6、堆排序

7、希爾排序

8、計數排序

9、基數排序

10、桶排序

總結： 目前並沒有十全十美的排序演算法，有優點就會有缺點，即便是快速排序演算法，也只是整體性能上優越，它也存在排序不穩定、需要大量的輔助空間、對少量數據排序無優勢等不鉛慧喊足。因此我們需要根據待排序數據的具體情況以及性能要求選擇合適的排序演算法。