js实现两种实用的排序算法——冒泡、选择法排序

梦里梦外; 2022-05-25 08:00 294阅读 0赞

一、冒泡排序

1、思路：

相邻两个数进行比较，前一个数比后一个数大，则交换两个数，依次类推。  
       具体解释  
        第一轮：  
        从第一个数朝最后一个数循环，然后比较相邻的两个数，如果前一个数比后一个数大，那么交换两个数，然后继续比较……，最大的数就存放在了最后一个位置  
         第二轮  
        从第一个数朝倒数第二个数循环，然后比较相邻的两个数，如果前一个数比后一个数大，那么交换两个数，然后继续比较。次大的数就存放在了倒数第二个位置   
        依次类推，就对数组进行的排序（从小到大）

2、举例说明（用示例推导冒泡的过程）

如：一组数： 9  6  8  2  5  1 ，进行冒泡排序的过程  
  
第一轮：  
i=0;  
5次  
第一次                第二次                            第三次  
j=0                       j=1                              j=2                        
比较第一位置     比较第二个位置              比较第三个位置  
和第二位置的数   和第三个位置的数           和第四个位置的数  
                                     
 9                           6                                           6                                          6           6           6  
 6                           9                                           8                                          8           8           8  
 8                           8                                           9                                          2           2           2  
 2                           2                                           2                                          9           5           5  
 5                           5                                           5                                          5           9           1  
 1                           1                                           1                                          1           1           9  
  
  
第二轮：  
i=1  
4次  
第一次                  第二次                             第三次  
比较第一位置        比较第二个位置               比较第三个位置  
和第二位置的数     和第三个位置的数           和第四个位置的数  
   
6                                         6                                            6                   6           6  
8                                         8                                            2                  2           2  
2                                         2                                            8                  5           5  
5                                         5                                            5                  8           1  
1                                         1                                            1                  1           8  
9                                         9                                            9                  9           9  
  
第三轮：  
i=2  
3次  
第一次                      第二次                                  第三次  
比较第一位置           比较第二个位置                     比较第三个位置  
和第二位置的数        和第三个位置的数                 和第四个位置的数  
   
6                                          2                                             2                2  
2                                          6                                             5                5  
5                                          5                                             6                1  
1                                          1                                             1                6  
8                                          8                                             8                8  
9                                          9                                             9                9  
  
依次类推……………………………………  
  
  
一共五轮。  
  
1  
2  
5  
6  
8  
9

3、代码：

二、选择法排序

1、思路：

每次找到最小的数放在最开始的位置，

详细解释：

1、找到最小的数，放在第一个位置（和第一个位置上的数交换）  
       2、找到次小的数，放在第二个位置（和第二个位置上的数交换）（在剩下数中，找到最小的数，放在第一个位置）

以此类推

2、举例说明：

假如一组数：9  6  8  2  5   1     3

//第一轮  
i=0  
//  从第一个位置(下标为0)朝最后一个数，找最小数(的下标)，和第一个位置(下标为0)上的数交换  
  1  6  8  2  5  9  3  
    
//第二轮  
i=1  
//  从第二个位置(下标为1)朝最后一个数，找最小数(的下标)，和第二个位置(下标为1)上的数交换  
  1  2  8  6  5  9  3  
    
//第三轮  
i=2  
//  从第三个位置(下标为2)朝最后一个数，找最小数(的下标)，和第三个位置(下标为2)上的数交换  
  1  2  3  6  5  9  8

以此类推,一共做6轮

3、代码：

<input type="button" value="排序" οnclick="mySort()" />
    
    function mySort(){
    	var arr=[9,6,8,2,5,1,3];
    	
    	for(var i=0;i<arr.length-1;i++){
    	    //1、从下标为i开始朝最后一数，找到最小的数的下标
    		var minIndex = i;//假定下标为i的数是最小数。
    		for(var j=i+1;j<arr.length;j++){
    			if(arr[j]<arr[minIndex]){
    				minIndex = j;
    			}
    		}
    
    		//2、放到下标为i的位置（把数组里最小的数和下标为i的数进行交换）
    		var temp = arr[i];
    		arr[i] =  arr[minIndex];
    		arr[minIndex] = temp;
    	}
    	
    	document.write(arr);
    }