排序

前沿

假如我想买一件衣服，我想在淘宝上去搜索，搜索有发现有很多，该如何去选择。其实我就想买一件便宜点，衣服质量还可以的，想找信誉好的商家，如何做？
网上搜索一下该如何做，万能的网络给我出了个注意，可以通过排序，可以按照信用、价格等进行排序之后，优先选择合适的放在最前面
此时就需要引入需要学习的东西---排序

排序的概念

• 排序是将一批无序的记录（数据）重新排列成按关键字有序的记录序列的过程。
• 排序的稳定性
• 内排序和外排序

排序的分类：

• 冒泡排序
• 选择排序
• 直接插入排序
• 希尔排序
• 堆排序排序
• 归并排序
• 快速排序

冒泡排序

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

选择排序

public static void selectionSort(int[] arr){
       
       for (int i = 0; i < arr.length - 1; i++) {    
            int  min = i;
            for (int j = i + 1; j < arr.length; j++) {
                  if (arr[min] > arr[j]) {
                       min = j;
                  }
            }
            if (min != i) {
               int tmp = arr[min];
               arr[min] = arr[i];
               arr[i] = tmp;
            }             
      }

}

直接插入排序

public class InsertSort{
    
    public void insertSort(int[] array){
        for(int i=1;i<array.length;i++)//第0位独自作为有序数列，从第1位开始向后遍历
        {
            if(array[i]<array[i-1])//0~i-1位为有序，若第i位小于i-1位，继续寻位并插入，否则认为0~i位也是有序的，忽略此次循环，相当于continue
            {
                int temp=array[i];//保存第i位的值
                int j = i - 1;
                while(j>=0 && temp<array[j])//从第i-1位向前遍历并移位，直至找到小于第i位值停止
                {
                    array[j+1]=array[j];
                    j--;
                }
                array[j+1]=temp;//插入第i位的值
            }
        } 
    }
    
    public static void printArray(int[] array) {
          for (int i = 0; i < array.length; i++) {
               System.out.print(array[i]);
               if (i != array.length - 1) {
                System.out.print(",");
               }
          }
     }
}

希尔排序

• code

public static void main(String[] args){
    int[] array={49,38,65,97,76,13,27,49,78,34,12,64,1};
        System.out.println("排序之前：");
        for(int i=0;i<array.length;i++){
            System.out.print(array[i]+" ");
        }
        //希尔排序
        int gap = array.length;
        while (true) {    
            gap /= 2;   //增量每次减半    
            for (int i = 0; i < gap; i++) {        
                for (int j = i + gap; j < array.length; j += gap) {//这个循环里其实就是一个插入排序            
                    int temp = array[j];            
                    int k = j - gap;            
                    while (k >= 0 && array[k] > temp) {                
                        array[k + gap] = array[k];                
                        k -= gap;            
                    }            
                    array[k + gap] = temp;        
                }    
            }    
            if (gap == 1)        
                break;
        }

        System.out.println();
        System.out.println("排序之后：");
        for(int i=0;i<array.length;i++){
            System.out.print(array[i]+" ");
        }
    }

堆排序排序

/**
    * 选择排序-堆排序
    * @param array 待排序数组
    * @return 已排序数组
    */
    public static int[] heapSort(int[] array) {
        //这里元素的索引是从0开始的,所以最后一个非叶子结点array.length/2 - 1
        for (int i = array.length / 2 - 1; i >= 0; i--) {  
            adjustHeap(array, i, array.length);  //调整堆
        }
  
        // 上述逻辑，建堆结束
        // 下面，开始排序逻辑
        for (int j = array.length - 1; j > 0; j--) {
            // 元素交换,作用是去掉大顶堆
            // 把大顶堆的根元素，放到数组的最后；换句话说，就是每一次的堆调整之后，都会有一个元素到达自己的最终位置
            swap(array, 0, j);
            // 元素交换之后，毫无疑问，最后一个元素无需再考虑排序问题了。
            // 接下来我们需要排序的，就是已经去掉了部分元素的堆了，这也是为什么此方法放在循环里的原因
            // 而这里，实质上是自上而下，自左向右进行调整的
            adjustHeap(array, 0, j);
        }
        return array;
    }
  
    /**
    * 整个堆排序最关键的地方
    * @param array 待组堆
    * @param i 起始结点
    * @param length 堆的长度
    */
    public static void adjustHeap(int[] array, int i, int length) {
        // 先把当前元素取出来，因为当前元素可能要一直移动
        int temp = array[i];
        for (int k = 2 * i + 1; k < length; k = 2 * k + 1) {  //2*i+1为左子树i的左子树(因为i是从0开始的),2*k+1为k的左子树
            // 让k先指向子节点中最大的节点
            if (k + 1 < length && array[k] < array[k + 1]) {  //如果有右子树,并且右子树大于左子树
                k++;
            }
            //如果发现结点(左右子结点)大于根结点，则进行值的交换
            if (array[k] > temp) {
                swap(array, i, k);
                // 如果子节点更换了，那么，以子节点为根的子树会受到影响,所以，循环对子节点所在的树继续进行判断
                    i  =  k;
                        } else {  //不用交换，直接终止循环
                break;
            }
        }
    }
  
    /**
    * 交换元素
    * @param arr
    * @param a 元素的下标
    * @param b 元素的下标
    */
    public static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

归并排序

public class MergeSort {   
    public static int[] mergeSort(int[] nums, int l, int h) {
        if (l == h)
            return new int[] { nums[l] };
        
        int mid = l + (h - l) / 2;
        int[] leftArr = mergeSort(nums, l, mid); //左有序数组
        int[] rightArr = mergeSort(nums, mid + 1, h); //右有序数组
        int[] newNum = new int[leftArr.length + rightArr.length]; //新有序数组
        
        int m = 0, i = 0, j = 0; 
        while (i < leftArr.length && j < rightArr.length) {
            newNum[m++] = leftArr[i] < rightArr[j] ? leftArr[i++] : rightArr[j++];
        }
        while (i < leftArr.length)
            newNum[m++] = leftArr[i++];
        while (j < rightArr.length)
            newNum[m++] = rightArr[j++];
        return newNum;
    }
    public static void main(String[] args) {
        int[] nums = new int[] { 9, 8, 7, 6, 5, 4, 3, 2, 10 };
        int[] newNums = mergeSort(nums, 0, nums.length - 1);
        for (int x : newNums) {
            System.out.println(x);
        }
    }
}

快速排序

    public static int[] qsort(int arr[], int start, int end) {
        int pivot = arr[start];
        int i = start;
        int j = end;
        while (i < j) {
            while ((i < j) && (arr[j] > pivot)) {
                j--;
            }
            while ((i < j) && (arr[i] < pivot)) {
                i++;
            }
            if ((arr[i] == arr[j]) && (i < j)) {
                i++;
            } else {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        if (i - 1 > start) arr = qsort(arr, start, i - 1);
        if (j + 1 < end) arr = qsort(arr, j + 1, end);
        return (arr);
    }

    public static void main(String[] args) {
        int arr[] = new int[]{3, 3, 3, 7, 9, 122344, 4656, 34, 34, 4656, 5, 6, 7, 8, 9, 343, 57765, 23, 12321};
        int len = arr.length - 1;
        arr = qsort(arr, 0, len);
        for (int i : arr) {
            System.out.print(i + "\t");
        }
    }


    /*//////////////////////////方式二////////////////////////////////*/
    更高效点的代码：(TextendsComparable和SortUtil都是自己封装的类，里面重写和实现了compareTo和swap方法)
    public <TextendsComparable<?superT>>

    T[] quickSort(T[] targetArr, int start, int end) {
        inti = start + 1, j = end;
        T key = targetArr[start];
        SortUtil<T> sUtil = new SortUtil<T>();

        if (start == end) return (targetArr);


        /*从i++和j--两个方向搜索不满足条件的值并交换
         *
         *条件为：i++方向小于key，j--方向大于key
         */
        while (true) {
            while (targetArr[j].compareTo(key) > 0) j--;
            while (targetArr[i].compareTo(key) < 0 && i < j) i++;
            if (i >= j) break;
            sUtil.swap(targetArr, i, j);
            if (targetArr[i] == key) {
                j--;
            } else {
                i++;
            }
        }

        /*关键数据放到‘中间’*/
        sUtil.swap(targetArr, start, j);

        if (start < i - 1) {
            this.quickSort(targetArr, start, i - 1);
        }
        if (j + 1 < end) {
            this.quickSort(targetArr, j + 1, end);
        }

        returntargetArr;
    }


    /*//////////////方式三：减少交换次数，提高效率/////////////////////*/
    private<TextendsComparable<?superT>>

    voidquickSort(T[] targetArr, intstart, intend) {
        inti = start, j = end;
        Tkey = targetArr[start];

        while (i < j) {
            /*按j--方向遍历目标数组，直到比key小的值为止*/
            while (j > i && targetArr[j].compareTo(key) >= 0) {
                j--;
            }
            if (i < j) {
                /*targetArr[i]已经保存在key中，可将后面的数填入*/
                targetArr[i] = targetArr[j];
                i++;
            }
            /*按i++方向遍历目标数组，直到比key大的值为止*/
            while (i < j && targetArr[i].compareTo(key) <= 0)
                /*此处一定要小于等于零，假设数组之内有一亿个1，0交替出现的话，而key的值又恰巧是1的话，那么这个小于等于的作用就会使下面的if语句少执行一亿次。*/ {
                i++;
            }
            if (i < j) {
                /*targetArr[j]已保存在targetArr[i]中，可将前面的值填入*/
                targetArr[j] = targetArr[i];
                j--;
            }
        }
        /*此时i==j*/
        targetArr[i] = key;//应加判断

        /*递归调用，把key前面的完成排序*/
        this.quickSort(targetArr, start, i - 1);


        /*递归调用，把key后面的完成排序*/
        this.quickSort(targetArr, j + 1, end);
//两个递归应加判断
    }