三大排序

蔚落 2021-12-12 23:29 104阅读 0赞

冒泡排序：

(外围只需遍历n-1次，最后一个元素自动就排好了)

基本思想：两个数比较大小，较大的数下沉，较小的数冒起来。  
过程：  
1、比较相邻的两个数据，如果第二个数小，就交换位置。  
2、从后向前两两比较，一直到比较最前两个数据。最终最小数被交换到起始的位置，这样第一个最小数的位置就排好了。

**或者**

3，从前往后，两两比较，最终最大的到了末尾位置，这样第一个最大数就排好了  
4、继续重复上述过程，依次将第2.3…n-1个最小数排好位置。

for(int i = 0;i < a.length-1 ;i++){ 
                for (int j = a.length - 1; j > i; j--) {
                    if (a[j] < a[j - 1]) {
                        int t = a[j];
                        a[j] = a[j - 1];
                        a[j - 1] = t;
                    }
                }
            }

选择排序：(外围只需遍历n-1次，最后一个元素自动就排好了)

每遍历一次都记住了当前最小元素的位置，最后仅需一次交换操作即可将其放到合适的位置。  
过程：  
1、（假定第一个数最小）在长度为N的无序数组中，第一次遍历n-1个数，找到最小的数值与第一个元素交换；  
2、第二次遍历n-2个数，找到最小的数值与第二个元素交换；  
3、第n-1次遍历，找到最小的数值与第n-1个元素交换，排序完成。

int[] a = {3,4,1,2,5}; 
            int temp = 0;
            for(int i=0;i<a.length-1;i++){
                int min = i;            //记录最小值的下标
                for(int j=i+1;j<a.length;j++){
                    if(a[j]<a[min]){
                        min = j;      //交换下标
                    }
                }
                if(min != i){       //如果最小值不是i，就把值进行交换
                    temp = a[i];
                    a[i] = a[min];
                    a[min] = temp; 
                }
            }

插入排序：用的增量法

打个比方：打牌

牌堆里的是无序，手上的有序，抓牌时与手上的牌进行比较(从左到右，从小到大)，再插入。（即分成两个区间，一个有序，一个无序）

第一张牌不用排！

int[] a = {3,4,1,2,5}; 
            
            for(int i=1;i<a.length;i++){  //抓牌
                int temp = a[i];     //要抓的牌交给一个变量
                int j= 0;
                for( j=i-1;j>=0 && a[j]>temp;j--){   //码牌
                    a[j+1] = a[j];
                    
                }
                a[j+1] = temp;
            }

转载于:https://www.cnblogs.com/wskb/p/10962699.html