排序算法（一）

2020-04-29

冒泡排序、堆排序、插入排序、归并排序

冒泡排序

平均时间复杂度O(n²) 空间复杂度O(1) 最好情况O(n) 最坏情况O(n²) 稳定

流程：

第一趟排序，把最大的数排到最后；第二趟排序，把第二大的数排到倒数第二位…

public static void BubbleSort(int[] arr){
    int temp = 0;
    boolean flag = false;   //标识，表示是否进行过交换
    for(int i=0;i<arr.length;i++){
        for(int j=0;j<arr.length-i-1;j++){
            if(arr[j]>arr[j+1]){    //若前数>后数，则交换
                flag = true;    //true表示进行过交换
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
        if(!flag){  //如果一趟排序里面没有进行过交换，证明已经有序
            break;
        }
        else{
            flag = false;
        }
    }
}

堆排序

平均时间复杂度O(nlogn) 空间复杂度O(1) 最好情况O(nlogn) 最坏情况O(nlogn) 不稳定

流程：

将无序序列构成一个堆，根据升序``降序需求选择大顶堆或小顶堆。
将堆顶元素与末尾元素交换，将最大元素“沉”到数组末端。
重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素。
反复执行调整+交换步骤，直到整个序列有序。

public static void heapSort(int[] arr){
    int temp = 0;
    //第一次对整个无序数组调整成大顶堆
    //从最后一个非叶子节点(arr.length/2-1 => 整个树的最后一个非叶子节点)，从右到左，从下到上
    for(int i=arr.length/2-1;i>=0;i--){
        adjustHead(arr,i,arr.length);
    }
    for(int j=arr.length-1;j>0;j--){
        //交换：此时第一个（堆顶）为最大值，交换到末尾
        temp = arr[0];
        arr[0] = arr[j];
        arr[j] = temp;
        //交换后末尾元素不用再管，只有堆顶改变了
        //只有堆顶不合格，其他都符合最大堆，只要把堆顶排到它适合的位置就好了
        //每次堆数组的长度都逐渐减小
        adjustHead(arr,0,j);
    }

}
/**
 * 功能：将以i对应的非叶子结点的树调整成大顶堆
 * @param arr 	 待调整的数组
 * @param i		 表示非叶子结点在数组中的索引
 * @param length 表示对多少个元素进行调整，length逐渐减小
 */
public static void adjustHead(int[] arr,int i,int length){
    int temp = arr[i];  //暂存当前值
    for(int k=i*2+1;k<length;k=k*2+1){ //k从i的左子节点开始(k=k*2+1 => k变成k的左子节点)
        if(k+1<length && arr[k]<arr[k+1]){ //比较i的左子节点和右子节点的大小
            k++; //k指向较大的节点
        }
        if(arr[k] > temp){ //判断较大节点和i的值的大小
            arr[i] = arr[k]; //若比i大，则大的值赋值给i
            i = k; //i指向k，继续往下循环比较
        }
        else{ //若比i小，则跳出（因为调整是从最后一个非叶子节点开始的）
            break;
        }
    }
    //当for完了，就已经将以i为父节点的树的最大值放在了最顶部（局部）
    arr[i] = temp; //将temp值放到调整后的位置
}

插入排序

平均时间复杂度O(n²) 空间复杂度O(1) 最好情况O(n) 最坏情况O(n²) 稳定

流程：

将数组分为有序区和无序区。
第一轮的有序区就是[0]。
每一轮从无序区中取第一个数与整个有序区的数从后往前进行比较。
找到适当的插入位置插入，有序区+1，无序区-1。

public static void insertSort(int[] arr){
    //进行n-1轮插入
    int insertVal = o;
    int insertIndex = 0;
    for(int i=1;i<arr.length;i++){
        insertVal = arr[i]; //存放无序区第一个数
        insertIndex = i-1; //无序区的前一个数，即有序区的最后一个数
        //给insertVal找到插入位置
        //1.insertIndex不能越界
        //2.arr[insertIndex]>insetVal表示还没有找到插入位置（改为<就是从小到大）
        //3.若没找到，则将insertIndex的值赋值给后一位，即值往后移
        while(insertIndex>=0 && arr[insertIndex]>insertVal){
            arr[insertIndex+1] = arr[insertIndex];
            insertIndex--;
        }
        //当循环结束，就找到了位置insertIndex+1
        //即待插入数>arr[insertIndex]或者insertIndex=-1，因此插入到它的后面一位
        arr[insertIndex+1] = insertVal;
    }
}

归并排序

平均时间复杂度O(n²) 空间复杂度O(n) 最好情况O(n) 最坏情况O(n²) 稳定

流程：分+治

分阶段：将数组进行划分，直到不能再划分。
治阶段：
1. 将已有序的子序列进行两两合并。
2. 遍历两个合并的子序列，按规则填充到temp数组中。
3. 填充完毕后temp数组中就是两个有序子序列合并后的有序序列。
4. 将temp数组中的元素复制回原数组的相应区间中。

//分+治
public static void mergeSort(int[] arr,int left,int right,int[] temp){
    while(left < right){    //进行分解
        int mid = (left + right) / 2;   //得到中间索引
        mergeSort(arr,left,mid,temp);   //对左区间继续分解
        mergeSort(arr,mid+1,right,temp);//对右区间继续分解
        merge(arr,left,mid,right,temp); //对左右区间进行合并
    }
}
//合并阶段
//原数组、左有序序列索引、中间索引、右边界、中转数组
public static void merge(int[] arr,int left,int mid,int right,int[] temp){
    int i = left;   //左有序序列的初始索引
    int j = mid + 1;//右有序序列的初始索引
    int t = 0;      //中转数组的初始索引
    //按照规则将左右有序序列的元素填充到temp中
    //直到其中一方填充完毕
    while(i<=mid && j<=right){
        if(arr[i] < arr[j]){    //左边的小则左边填充进temp
            temp[t++] = arr[i++];//后移
        }
        else{   //右边的小则填充进temp
            temp[t++] = arr[j++]; //后移
        }
    }
    while(i <= mid){    //若左有序序列还有剩余，则全部填充进temp
        temp[t++] = arr[i++];
    }
    while(j <= right){  //若右有序序列还有剩余，则全部填充进temp
        temp[t++] = arr[j++];
    }
    //将temp中的元素复制回原数组中对应的区间
    t = 0;  //初始化temp的索引
    int arrLeft = left; //从原数组的left开始到right这个区间进行复制
    while(arrLeft <= right){
        arr[arrLeft++] = temp[t++];
    }
}