堆排序-快排-冒泡

堆排序

堆排序：堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。

堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了

java代码实现堆排序的过程

首先，我们需要先交换每一个非叶子结点和他们的左右孩子节点，构造这三个节点为一个大顶堆.

以下代码的思想就是，交换结点以及他们左右孩子节点，找到最大值并交换位置

/**
    * 参数说明   arr 表示待构建数组
    * n：表示堆的元素个数
    * i: 表示每一个小堆的父节点
    */
   public static void heap_step(int[] arr, int n, int i) {
       int c1 = 2 * i + 1;    //i结点的左孩子
       int c2 = 2 * i + 2;   //i结点的右孩子
       int max = i;   //这三个元素最大值的下标指向

       //定义递归出口
       if (i > n) {
           return;
       }
       if (c1 < n && arr[c1] > arr[max]){
           max = c1;
       }
       if (c2 < n && arr[c2] > arr[max]) {
           max = c2;
       }
       if (max != i) {
           swap(arr, max, i);//交换两个位置的元素
           heap_step(arr, n, max);//继续进行递归判断，确保每一次构建完任意一个小堆都是大顶堆
       }

   }

   /*
       两个元素交换位置的函数
    */
   public static void swap(int[] arr,int i,int j){
       int temp = arr[i];
       arr[i] = arr[j];
       arr[j] = temp;
   }

上面的方法是构建结点以及孩子节点元素的交换步骤

下面我们需要，对数组中也就是完全二叉树中所有的非叶子结点，逐次遍历，对每一个非叶子结点都需要进行构造大顶堆的过程

/**
     * 我们需要对每一个非叶子结点以及他们的左右孩子构建大顶堆
     * 从最后一个非叶子结点开始
     * 最后一个叶子结点数组下标为：  last_node = arr.length-1
     * 则最后一个非叶子结点为   last_parent = (last_node-1)/2
     * @param arr
     * @param n
     */
    public static void build_heap(int[] arr, int n) {
        int last_node = n-1;
        int last_parent = (last_node-1)/2;
        //对每一个非叶子结点，依次从后向前遍历，每一个都做heap_step的大顶堆构建
        for (int i = last_parent; i >=0 ; i--) {
            heap_step(arr,n,i);
        }
    }

以上方法执行完，我们的数组完全二叉树就完全变成了一个大顶堆。每一个根节点都大于他们的左右孩子节点

构造完大顶堆之后，我们需要把大顶堆的根元素与最后一个位置的元素进行位置的交换。

交换代码如下：

/**
 * 构建完大顶堆之后，需要进行大顶堆的第一个元素与最后元素进行交换
 * @param arr
 */
public static void heap_sort(int[] arr,int n){
    build_heap(arr, arr.length);   //把数组先构造成为一个大顶堆
    // 这个时候数组已经是一个大顶堆了
    //交换数据
    for (int i = n - 1; i >= 0; i--) {
        swap(arr, i, 0);
        /*
            因为这个时候完全二叉树已经是一个大顶堆了，
            所以我们只需要使用heap_step交换最顶层的三个数字就可以,也就是最根节点以及它们的左右孩子节点
         */
        heap_step(arr, i, 0);
    }

}

上面是对排序中的各个步骤逐一的记录，下面是完整代码：

完整的堆排序算法如下：

package study;

public class heapSort {
    public static void main(String[] args) {
        int[] array = {12,15,10,18,6,9,16};
        heap_sort(array, array.length);
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i]+" ");
        }

    }
    
    /**
     * 参数说明   arr 表示待构建数组
     * n：表示堆的元素个数
     * i: 表示每一个小堆的父节点
     */
    public static void heap_step(int[] arr, int n, int i) {
        int c1 = 2 * i + 1;    //i结点的左孩子
        int c2 = 2 * i + 2;   //i结点的右孩子
        int max = i;   //这三个元素最大值的下标指向

        //定义递归出口
        if (i > n) {
            return;
        }
        if (c1 < n && arr[c1] > arr[max]){
            max = c1;
        }
        if (c2 < n && arr[c2] > arr[max]) {
            max = c2;
        }
        if (max != i) {
            swap(arr, max, i);//交换两个位置的元素
            heap_step(arr, n, max);//继续进行递归判断，确保每一次构建完任意一个小堆都是大顶堆
        }

    }

    /**
     * 我们需要对每一个非叶子结点以及他们的左右孩子构建大顶堆
     * 从最后一个非叶子结点开始
     * 最后一个叶子结点数组下标为：  last_node = arr.length-1
     * 则最后一个非叶子结点为   last_parent = (last_node-1)/2
     * @param arr
     * @param n
     */
    public static void build_heap(int[] arr, int n) {
        int last_node = n-1;
        int last_parent = (last_node-1)/2;
        //对每一个非叶子结点，依次从后向前遍历，每一个都做heap_step的大顶堆构建
        for (int i = last_parent; i >=0 ; i--) {
            heap_step(arr,n,i);
        }
    }

    /**
     * 构建完大顶堆之后，需要进行大顶堆的第一个元素与最后元素进行交换
     * @param arr
     */
    public static void heap_sort(int[] arr,int n){
        build_heap(arr, arr.length);   //把数组先构造成为一个大顶堆
        // 这个时候数组已经是一个大顶堆了
        //交换数据
        for (int i = n - 1; i >= 0; i--) {
            swap(arr, i, 0);
            /*
                因为这个时候完全二叉树已经是一个大顶堆了，
                所以我们只需要使用heap_step交换最顶层的三个数字就可以,也就是最根节点以及它们的左右孩子节点
             */
            heap_step(arr, i, 0);
        }

    }


    /*
        两个元素交换位置的函数
     */
    public static void swap(int[] arr,int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

快速排序

package study.Sort;

//快速排序
public class quickSort {

    public static void quickSortArray(int[] array,int low,int hight){

        int i,j,temp,t;
        if (low > hight) {
            return;
        }
        i = low;
        j = hight;
        temp = array[low];

        while (i < j) {
            while (temp<=array[j] && i < j) {
                j--;
            }
            while (temp>=array[i] && i < j) {
                i++;
            }
            if (i < j) {
                t = array[j];
                array[j] = array[i];
                array[i] = t;
            }
        }

        array[low] = array[i];
        array[i] = temp;
        quickSortArray(array,low,j-1);
        quickSortArray(array,j+1,hight);
    }
    public static void main(String[] args) {
        int[] array ={10,5,7,3,12,25,15,8};
        quickSortArray(array,0,array.length-1);
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i]+" ");
        }
    }

}

冒泡排序

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

选择排序

private static void select(int[] array) {
    for (int i = 0; i < array.length-1; i++) {
        int min = array[i];
        int minIndex = i;
        for (int j = i+1; j < array.length; j++) {
            if (min > array[j]) {
                min = array[j];
                minIndex = j;
            }
        }
        if (minIndex != i) {
            array[minIndex] = array[i];
            array[i] = min;
        }

    }
}