JAVA随时笔记(四)：常用的排序算法实现

「爱情、让人受尽委屈。」 2022-05-22 13:15 119阅读 0赞

### 1、冒泡排序 ###

原理：  
比较array\[n\]和array\[n+1\]的大小，把大的数交换到后面，即array\[n\]>array\[n+1\]，就交换。循环到数组最后，就可以把最大值找出来，放到array\[length-1\]上。  
第二次循环，把第二大的数交换到array\[length-2\]上面  
循环n-1次就把最大的n-1个数找出来，最小的数就在array\[0\]处。  
为了方便，这里把交换的函数抽出来，如下，后面的几个排序也会用到这个交换。

//冒泡排序
       public static void bubbleSort(int[] array){
            for(int i = 0,len = array.length-1;i<len;i++){
                for(int j = 0;j<len-i;j++){
                    if(array[j]>array[j+1]){
                        swap(array,j,j+1);
                    }
                }
            }
        }
    
       //交换数组中a位置和b位置的数
       public static void swap(int[] array,int a,int b){
            if(a!=b){
                array[a] = array[a] + array[b];
                array[b] = array[a] - array[b];
                array[a] = array[a] - array[b];
            }
        }

### 2、直接插入排序 ###

原理：  
确认array\[n\]的前面的数值都比array\[n\]小。  
第一次，比较array\[0\]和array\[1\]，把小的数交换到前面  
第二次，比较array\[2\]和它前面的数据，放到合适的位置。  
循环到最后，排序完成

/** * 直接插入排序 * @param array */
        public static void insertSort(int[] array){
            int temp;
            for(int i = 1,len = array.length;i<len;i++){
                int j = i-1;
                temp = array[i];
                for(;j>=0&&temp<array[j];j--){
                    array[j+1] = array[j];
                }
                array[j+1] = temp;
            }
        }

### 3、希尔排序（直接插入改进） ###

原理：  
希尔排序是把数组根据希尔值分成n个部分,进行排序，再把间隔减小，再排序，最后间隔为1，再排序整个数组就是有序的。  
如：  
数组长度为10，默认的希尔值是2，也可以直接根据情况选择其它数字。  
当希尔值为2时，间隔为10/2=5,把数组分成位置在\[0,5\],\[1,6\],\[2,7\],\[3,8\],\[4,9\]五个部分，对这五个分别进行排序，然后把上一次的间隔5/2(希尔值)=2作为间隔，分成\[0,2,4,6,8\]和\[1,3,5,7,9\]两个部分。分别进行排序。最后间隔为2/2=1，也就是整个数组进行直接插入排序。

/** * 希尔交换排序 * @param array * @param init */
        public static void shellSortSwap(int[] array,int init){
            for(int temp = array.length/init;temp>0;temp/=init){
                for(int i = temp;i<array.length;i++){
                    int j = i;
                    while(j-temp>0&&array[j]<array[j-temp]){
                        swap(array,j,j-temp);
                        j-=temp;
                    }
                }
            }
        }

### 4、选择排序 ###

原理：依次选出最小的数放到前面  
第一次，从位置0开始找出最小的数,记录位置，把最小的数与位置0的数进行交换  
第二次，从位置1开始………..。

/** * 选择排序 * @param array */
        public static void chooseSort(int[] array){
            int position;
            for(int i = 0,len = array.length;i<len;i++){
                int temp = array[i];
                position = i;
                for(int j = i+1;j<len;j++){
                    if(temp>array[j]){
                        temp = array[j];
                        position = j;
                    }
                }
                swap(array,i,position);
            }
        }

### 5、快速排序 ###

原理：  
1、先从数列中取出一个数作为基准数  
2、分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边  
3、再对左右区间重复第二步，直到各区间只有一个数

/** * 快速排序 * @param array * @param left * @param right */
        public static void quickSort(int[] array,int left,int right){
            if(left>right){
                return;
            }
            int i = left,j = right,temp = array[left];
            while (i!=j){
                while(array[j]>=temp&&i<j){
                    j--;
                }
                while (array[i]<=temp&&i<j){
                    i++;
                }
                if(i<j){
                    swap(array,i,j);
                }
            }
            array[left] = array[i];
            array[i] = temp;
            quickSort(array,left,i-1);
            quickSort(array,i+1,right);
        }