十大排序算法

---

1、堆排序

1.1 堆的定义

1.2 堆排序的思路（大顶堆）

（1）根据初始数组去构建初始堆。

（2）每次交换第一个和最后一个元素，输出最后一个元素（最大值），然后把剩下元素重新调整为大顶堆，再进行交换第一个元素和最后一个元素，再调整大顶堆，重复执行，直到整个数组排序完成。

1.2.1 建堆的过程：

代码：

• 初始建堆

// 1.初始建堆
// 从最后一个非叶子节点开始，到根节点结束
for (int i = arr.length/2 -1; i >=0; i--) {
    // 左右孩子如果比i大，交换
    heapify(arr,i,arr.length - 1);
}

• 左右孩子如果比i大，交换

// 左右孩子如果比i大，交换
// 其中last_index是用来判断i节点是否有左右孩子，因为是完全二叉树
private void heapify(int[] arr, int i, int last_index) {
    int max = i;
    // 如果i的左右孩子存在的话，因为是完全二叉树，它的左右孩子节点索引一定小于等于最后一个节点的索引
    // 判断i的左孩子是否大于它
    if ((2*i+1) <= last_index && arr[2*i+1] > arr[max]) {
        max = 2*i+1;
    }
    // 判断i的右孩子是否大于它
    if ((2*i+2) <= last_index && arr[2*i+2] > arr[max]) {
        max = 2*i+2;
    }
    // 如果max不是i，说明他的孩子节点有比他大，将i和max交换
    if (max != i) {
        swap(arr,i,max);
        heapify(arr,max,last_index);
    }
    return;
}

1.2.2 堆排序的过程：

代码：

// 2.堆排序的过程
for (int i = arr.length - 1; i > 0; i--) {
    // 交换当前节点和堆顶节点
    swap(arr,i,0);
    // 只需判断头节点，使得该树再次变为大顶堆
    heapify(arr,0,i - 1);
}

完整代码：

public class HeapSort {

    // @Test
    // public void test() {
        // int[] arr = {27,46,12,33,49,27,36,40,42,50,51};
        // heapSort(arr);
        // System.out.println(Arrays.toString(arr));
    // }


    public void heapSort(int[] arr) {
        // 1.初始建堆
        // 从最后一个非叶子节点开始，到根节点结束
        for (int i = arr.length/2 -1; i >=0; i--) {
            // 左右孩子如果比i大，交换
            heapify(arr,i,arr.length - 1);
        }
        // 2.堆排序的过程
        for (int i = arr.length - 1; i > 0; i--) {
            // 交换当前节点和堆顶节点
            swap(arr,i,0);
            // 只需判断头节点，使得该树再次变为大顶堆
            heapify(arr,0,i - 1);
        }
    }

    // 左右孩子如果比i大，交换
    // 其中last_index是用来判断i节点是否有左右孩子，因为是完全二叉树
    private void heapify(int[] arr, int i, int last_index) {
        int max = i;
        // 如果i的左右孩子存在的话，因为是完全二叉树，它的左右孩子节点索引一定小于等于最后一个节点的索引
        // 判断i的左孩子是否大于它
        if ((2*i+1) <= last_index && arr[2*i+1] > arr[max]) {
            max = 2*i+1;
        }
        // 判断i的右孩子是否大于它
        if ((2*i+2) <= last_index && arr[2*i+2] > arr[max]) {
            max = 2*i+2;
        }
        // 如果max不是i，说明他的孩子节点有比他大，将i和max交换
        if (max != i) {
            swap(arr,i,max);
            heapify(arr,max,last_index);
        }
        return;
    }

    // 交换函数
    private void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

1.3 算法稳定性(不稳定)

​ 在建立堆的调整步骤里,由于关键字相同的两个记录位置并不会被调换,所以建堆的时候是稳定的。但是,在堆顶与堆尾交换的时候两个相等的记录在例中的相对位置就可能发生改变,这就影响其稳定性了。

1.4 时间复杂度

​ 堆排序包括两个阶段,初始化建堆和重建堆。所以堆排序的时间复杂度由这两方面组成。
​ 初始化建堆的时间复杂度为O(n) ,排序重建堆的时间复杂度为O(nlogn) ,所以总的时间复杂度为O(n+nlogn)=**O(nlogn)**。

2、冒泡排序

2.1 思路

// 冒泡排序
public class Bubbling {
    public static void main(String[] args) {
        int[] arr = {67,42,88,16,25,3};
        // 外层循环控制趟数，趟数是5趟
        for (int i = 0; i < arr.length - 1; i++) {
            // 内层控制比较的次数
            for (int j = 0; j < arr.length - 1 - i; j++) {
                // 比较数的大小
                if (arr[j] > arr[j + 1]) {
                    // 如果数组j大于数组j+1，交换
                    int tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                }

            }
        }
     }
}

2.2 算法稳定性

​ 如果待排序的序列中存在两个或两个以上具有相同关键词的数据，排序后这些数据的相对次序保持不变,通俗地讲，就是两个相同的数的相对顺序不会发生改变，则该算法是稳定的；冒泡排序足稳定的排序算法。

2.3 时间复杂度

​ 对于n位的数列则有比较次数为(n-1) + (n-2)+ ..+ 1=n*(n- 1)/2.这就得到了最大的比较次数, n(n-1)/2 =
(n^2 - n)/2,计算时间复杂度的时候,忽略常数项1/2,再忽略低阶项n ,得到冒泡排序的时间复杂度为0(n^2)

3、选择排序

选择排序： 通过一趟遍历，找到最小值的下标。 和下标为0的元素交换。 下一趟，从剩下的元素（排除下标0）， 找到最小值的下标，然后和下标为1的交换。 特点：比较的次数没有减少，但是交换次数一趟只交换一回。

// 选择排序
public class selectSort {
    public static void main(String[] args) {
        int[] a = {35,22,17,41,72,29,10};
        // 外层循环控制趟数n个数，只需n-1趟
        for (int i = 0; i < a.length - 1; i++) {
            // 假定最小值为a[i]
            int min = a[i];
            // 假定最小值的索引为i
            int index = i;

            // 遍历数组找到最小值
            for (int j = i + 1; j < a.length; j++) {
                if (a[j] < min) {
                    min = a[j];
                    index = j;
                }
            }
            
            // 让最小值和当前a[i]进行交换
            int temp = a[index];
            a[index] = a[i];
            a[i] = temp;
        }

      
    }
}

4、快速排序

public class quickSort {
    public static void main(String[] args) {
        int[] a = {23,-9,78,3,34,3,0,34,23};
        quickSort(a,0,a.length - 1);
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }
    }

    static void quickSort(int[] arr, int left, int right) {
        if (left >= right) {
            // 递归退出条件
            return;
        }
        int l = left;
        int r = right;

        while(l < r) {
            // l < r，如果r指向的值大于left（最左端的值），r就一直减，直到小于
            while (l < r && arr[r] >= arr[left]) r--;
            // l < r，如果r指向的值小于left（最左端的值），l就一直加，直到大于
            while (l < r && arr[l] <= arr[left]) l++;

            // 如果l == r，则与left交换，使得l左边一定小于l，右边一定大于l
            if (l == r) {
                int temp = arr[l];
                arr[l] = arr[left];
                arr[left] = temp;
            }else { // 否则，l和r交换，使得他们左是小，右是大
                int temp = arr[l];
                arr[l] = arr[r];
                arr[r] = temp;
            }
        }
        // 此时l一定和r指向同一位置
        // 递归l左
        quickSort(arr,left,l - 1);
        // 递归l右
        quickSort(arr,l + 1,right);
    }
}

2.2 算法稳定性

​ 如果待排序的序列中存在两个或两个以上具有相同关键词的数据，排序后这些数据的相对次序保持不变,通俗地讲，就是两个相同的数的相对顺序不会发生改变，则该算法是稳定的；冒泡排序足不稳定的排序算法。

2.3 时间复杂度

5、插入排序

5.1 思路

​ 假设前面 n-1(其中 n>=2)个数已经是排好顺序的，现将第 n 个数插到前面已经排好的序列中，然后找到合适自己的位置，使得插入第n个数的这个序列也是排好顺序的。

代码：

// 插入排序
public class insertSort {
    public static void main(String[] args) {
        int[] a = {23,-9,78,3,34,3,0,34,23};
        insertSort(a);
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }
    }

    static void insertSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            for (int j = i ; j > 0 ; j--) {
                if (arr[j] < arr[j - 1]) {
                    int tmp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = tmp;
                }else {
                    break;
                }
            }

        }
    }


}

5.2 算法稳定性

​ 如果待排序的序列中存在两个或两个以上具有相同关键词的数据，排序后这些数据的相对次序保持不变,通俗地讲，就是两个相同的数的相对顺序不会发生改变，则该算法是稳定的；冒泡排序足稳定的排序算法。

5.3 时间复杂度

插入排序的平均时间复杂度也是 **O(n^2)**，空间复杂度为常数阶 **O(1)**，具体时间复杂度和数组的有序性也是有关联的。

插入排序中，当待排序数组是有序时，是最优的情况，只需当前数跟前一个数比较一下就可以了，这时一共需要比较 N-1 次，时间复杂度为 **O(N)**。最坏的情况是待排序数组是逆序的，此时需要比较次数最多，最坏的情况是 **O(n^2)**。