《算法设计与分析》

1.冒泡排序

1. 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
3. 针对所有的元素重复以上的步骤，除了最后一个；
4. 重复步骤1~3，直到排序完成。

public static void bubbleSort(int[] arr) {
	int temp = 0;//用于辅助交换的变量
    for(int i = 0; i<arr.length-1;i++){//一轮排好一个，n个数只需排n-1轮
		for(int j =0;j<arr.length-1-i;j++){
            //如果前面数大于后面，则交换
            if(arr[j] > arr[j+1]){
                temp=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=temp;
            }
        }
    }
}

2.选择排序

1. 在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
2. 从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾
3. 重复第二步，直到所有元素均排序完毕。

public static void selectionSort(int[] arr) {
    //int temp, min = 0;
    for (int i = 0; i < arr.length - 1; i++) { // 总共要经过 n-1 轮比较,最后一个不用比
        int min = i;
        
        for (int j = i + 1; j < arr.length; j++) { //从i的下一个到最后循环查找最小值
            if (arr[min] > arr[j]) {
                min = j;
            }
        }
        if (min != i) { // 将找到的最小值和i位置所在的值进行交换
            int temp = arr[i];
            arr[i] = arr[min];
            arr[min] = temp;
        }
    }
}

3.插入排序

1. 把待排序的数组分成已排序和未排序两部分，初始的时候把第一个元素认为是已排好序的。
2. 从第二个元素开始，在已排好序的子数组中寻找到该元素合适的位置并插入该位置。
3. 重复上述过程直到最后一个元素被插入有序子数组中。

public static void insertionSort(int[] arr){
    // 从下标为1的元素开始选择合适的位置插入，因为下标为0的只有一个元素，默认是有序的
    for (int i=1; i<arr.length; i++){ // 循环到最后
        int value = arr[i]; // 记录要插入的数据
        int position=i;
        // 从已经排序的序列最右边的开始比较，找到比其小的数
        while (position>0 && arr[position-1]>value){ 
            arr[position] = arr[position-1]; //挪动
            position--;
        }
        arr[position] = value; //插入
    }
}

4.归并排序

• 递归法（Top-down）（归并的步骤）:

1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置
3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
4. 重复步骤3直到某一指针到达序列尾
5. 将另一序列剩下的所有元素直接复制到合并序列尾

public static void mergeSort(int[] arr){
    int[] temp =new int[arr.length];//作为每次合并时的临时数组
    internalMergeSort(arr, temp, 0, arr.length-1);
}
private static void internalMergeSort(int[] arr, int[] temp, int left, int right){
    //当left==right的时，已经不需要再划分了
    if (left<right){
        int middle = (left+right)/2;
        internalMergeSort(arr, temp, left, middle);        //左子数组
        internalMergeSort(arr, temp, middle+1, right);     //右子数组
        mergeSortedArray(arr, temp, left, middle, right);  //合并两个子数组，temp数组此用
    }
}
// 合并两个有序子序列
private static void mergeSortedArray(int arr[], int temp[], int left, int middle, int right){
    int i=left;      
    int j=middle+1;
    int k=0;
    while (i<=middle && j<=right){
        temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
    }
    while (i<=middle){
        temp[k++] = arr[i++];
    }
    while (j<=right){
        temp[k++] = arr[j++];
    }
    //把数据复制回原数组
    for (i=0; i<k; ++i){
        arr[left+i] = temp[i];
    }
}

5.快速排序

1. 从数列中挑出一个元素，称为"基准"（pivot）；
2. 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
3. 递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。

public static void quickSort(int[] arr){
    qSort(arr, 0, arr.length-1);
}
private static void qSort(int[] arr, int low, int high){
    if(low<high){
        int pivot = partition(arr, low, high);        //将数组分为两部分
        qSort(arr, low, pivot-1);                   //递归排序左子数组
        qSort(arr, pivot+1, high);                  //递归排序右子数组
	}
}
private static int partition(int[] arr, int low, int high){//双向扫描版
    int i = low,
        j = high+1;
    int x = arr[low];     //基准
    //将<x的元素交换到左边
    //将>x的元素交换到右边
    while(true){
        while(arr[++i]<x && i<high);
        while(arr[--j]>x);//直到i，j都不满足时交换；注意右指针j的放后面
        if(i>=j) break;
        swap(arr,i,j);
    }
    arr[low]=arr[j];//结束，交换arr[j]与arr[low]
    arr[j]=x;
    return j;//返回划分点，此时左半段小于x，右半段大于x
}
private static void swap(int[] a,int p ,int r){
    int temp = a[p];
    a[p]=a[r];
    a[r]=temp;
}

6.堆排序

堆排序原理

堆（Heap）是一种基于完全二叉树的数据结构，二叉树可以链式存储，也可以顺序存储（数组）。它分为最大堆和最小堆。常被用来实现优先队列，也可以用来实现堆排序算法。 **最大堆：**堆中每个父节点的元素值都大于等于其孩子结点（如果存在）。 **需要注意：**数组都是 Zero-Based，因此堆数据结构模型要发生改变 相应的，几个计算公式也要作出相应调整：

• Parent(i) = floor((i-1)/2)，i 的父节点下标
• Left(i) = 2i + 1，i 的左子节点下标
• Right(i) = 2(i + 1)，i 的右子节点下标

**堆排序：**把最大堆堆顶的最大数取出，将剩余的堆继续调整为最大堆，再次将堆顶的最大数取出，这个过程持续到剩余数只有一个时结束。 **最大堆调整：**删除根元素后其他元素还保持堆的性质，把最后一个元素放到堆顶，自上而下比较，不断将父节点与最大的子节点调换位置，直到数组恢复堆的性质。

堆排序代码

1.构造一个最大堆（大顶堆），取堆顶数字（也就是最大值）到数组末尾（交换数据）； 2.再将剩下的数字构建一个最大堆，取堆顶数字（剩下值中的最大值）到数组次末尾； 3.重复以上操作，直到取完堆中数字，最终得到一个从小到大的序列。

class ArrayHeap {
    private int[] arr;

    public int[] getArr() {
        return arr;
    }

    public ArrayHeap(int[] arr) {
        this.arr = arr;
    }

    private int getParentIndex(int child) {
        return (child - 1) / 2;
    }

    private int getLeftChildIndex(int parent) {
        return 2 * parent + 1;
    }

    private void swap(int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    /**
     * 调整堆，自上而下
     */
    private void adjustHeap(int i, int len) {
        int left, right, j;
        left = getLeftChildIndex(i);
        while (left <= len) {
            right = left + 1;
            j = left;
            if (j < len && arr[left] < arr[right]) {
                j++;
            }
            if (arr[i] < arr[j]) {
                swap(i, j);
                i = j;
                left = getLeftChildIndex(i);
            } else {
                break; // 停止筛选
            }
        }
    }

    /**
     * 堆排序
     */
    public void sort() {
        int last = arr.length - 1;
        // 初始化最大堆
        for (int i = getParentIndex(last); i >= 0; --i) {
            adjustHeap(i, last);//以父节点为基础，每次都自上而下调整
        }
        // 堆调整，每次循环将最大值放到未排序数组最后
        while (last >= 0) {
            swap(0, last--);
            adjustHeap(0, last);
        }
    }
}

7.希尔排序（插入排序的改良版）

希尔排序的提出，主要基于以下两点：

• 插入排序算法在数组基本有序的情况下，可以近似达到O(n)复杂度，效率极高。
• 但插入排序每次只能将数据移动一位，在数组较大且基本无序的情况下性能会迅速恶化。

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：

1. 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
2. 按增量序列个数k，对序列进行 k 趟排序；
3. 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

增量采用delta/=2方式，时间复杂度还是O(n2)：

public static void shellSort(int[] arr){
    int temp;
    for (int delta = arr.length/2; delta>=1; delta/=2){ //对每个增量进行一次排序
        for (int i=delta; i<arr.length; i++){              
            for (int j=i; j>=delta && arr[j]<arr[j-delta]; j-=delta){ //注意每个地方增量和差值都是delta
                temp = arr[j-delta];
                arr[j-delta] = arr[j];
                arr[j] = temp;
            }
        }//loop i
    }//loop delta
}

不同增量方式，时间复杂度不同

不同算法对比