排序算法

一、插入排序

1、代码如下：

public static void insertSort1(int[] ints) {
        //i循环：从索引1开始一直到最后
                for(int i=1;i<ints.length;i++) {
                    if(ints[i] < ints[i-1]) {//i位置的值需要插入到前面位置
                        //j循环：从0开始到i前面
                        for(int j=0;j<i;j++) {
                            if(ints[i] < ints[j]) {//找到插入位置(j位置)
                                int temp = ints[i];
                                //k循环：将数据向后移动
                                for(int k=i-1;k >= j;k--) {
                                    ints[k+1] = ints[k];
                                }
                                ints[j] = temp;
                                break;
                            }
                        }
                    }
                }
    }

2、其实2个for循环也可以解决，代码如下：

public static void insertSort2(int[] ints) {
        
        for(int i = 1;i < ints.length;i++) {
            if(ints[i] < ints[i-1]) {
                for(int j = 0;j< i; j++) {
                    if(ints[i] < ints[j]) {
                        int temp = ints[i];
                        ints[i] = ints[j];
                        ints[j] = temp;
                    }
                }
            }
        }
    }

二、快速排序

   /**
     * 快速排序
     * @param ints 需要排序的数组
     * @param start 开始位置
     * @param end 结束位置
     */
    public static void fastSort(int[] ints,int start,int end) {
        if(start < end) {
            int index = sortUnit(ints, start, end);//获取标杆值所在的位置
            fastSort(ints, start, index-1);//左边
            fastSort(ints, index+1, end);//右边
        }
        
    }
    /**
     * 返回标杆值在数组中的位置
     * @param ints 需要排序的数组
     * @param start 开始位置
     * @param end 结束位置
     * @return
     */
    public static int sortUnit(int[] ints,int start,int end) {
         int temp = ints[start];
         int j = end;
         int i = start;
         while(i<j) {
             while(i<j) {
                 if(ints[j] < temp) {//j负责找到比标杆小的数，扔给i
                     ints[i] = ints[j];
                     break;
                 }
                 j--;
             }
             while(i<j) {
                 if(ints[i] >= temp) {//j负责找到比标杆大的数，扔给j
                     ints[j] = ints[i];
                     break;
                 }
                 i++;
             }
         }
         ints[i] = temp;//将标杆值放入到数组中
        return i;
    }

三、堆排序

public static void stackSort(int[] ints) {
        int size = ints.length;
        while(size>2) {
            //建最大堆
            //循环次数：父节点的个数，父节点索引
            for(int i = (size-1)/2;i>=1;i--) {
                int maxIndex = i*2;//假设做儿子最大
                //左儿子=父节点索引*2，右儿子=左儿子+1
                if((maxIndex+1) < size && ints[maxIndex+1] > ints[maxIndex]) {//假设有右儿子且右儿子比左儿子大
                    maxIndex++;//右儿子大
                }
                //最大的儿子与父亲比
                if(ints[maxIndex] > ints[i]) {
                    int temp = ints[maxIndex];
                    ints[maxIndex] = ints[i];
                    ints[i] = temp; 
                }
            }
            //根节点与最后一个节点交换
            int data = ints[1];
            ints[1] = ints[size-1];
            ints[size-1] = data;
            size--;
        }
    }
注：堆排序对数组的第一个元素不进行处理

四、冒泡排序

public static void bubbleSort(int[] ints) {
        for(int i=0;i<ints.length-1;i++) {
            for(int j=0;j<ints.length-1-i;j++) {
                if(ints[j+1] < ints[j]) {
                    int temp = ints[j+1];
                    ints[j+1] = ints[j];
                    ints[j] = temp;
                }
            }
        }
    }