排序实现

排序算法的稳定性是根据相同数值的元素之间的相对位置进行判断。

int main(){
    int nums[] = {12,21,11,0,8,53};
    int size = sizeof(nums)/ sizeof(int);
//    SelectSort(nums, size);
//    mopoSort(nums, size);
//    insertSort(nums,size);
    quickSort(nums,size);
    listNum(nums,size);
    return 0;

}

/**
 * 快速排序  [是一种基于分治思想的排序算法]
 *      1. 选取数组最左端元素作为基准数，初始化两个指针 i 和 j 分别指向数组的两端；
        2. 设置一个循环，在每轮中使用 i（j）分别寻找第一个比基准数大（小）的元素，然后交换这两个元素；
        3. 循环执行步骤 2. ，直到 i 和 j 相遇时停止，最后将基准数交换至两个子数组的分界线；
 * @param nums 数组
 * @param size 大小
 */
void quickSort(int nums[] , int size){
    quick(nums, 0 , size - 1);
}

void quick(int *nums, int left , int right ){
    if (left >= right){
        return;
    }
    //进行划分
    int mid = partition(nums,left,right);
    //递归左右子数组
    quick(nums,left, mid);
    quick(nums, mid +1 ,right);
}


//进行划分
int partition(int nums[] , int left , int right){
    int i = left;
    int j = right;
    while(i < j){
        while(i < j && nums[j] >= nums[left]){
            j--;    //从右向左找小于基准数的数
        }
        while(i < j && nums[left] >= nums[i]){
            i++;    //从左向右找大于基准数的数
        }
        swap(nums,i,j);
    }
    swap(nums,i, left);
    return i;
}

void swap(int nums[], int left , int right){
    int temp = nums[left];
    nums[left] = nums[right];
    nums[right] = temp;
}

/**
 * 选择排序
 *      实现思路
 *        首先进行遍历循环当前数组， 没遍历到一个数， 就以这个数为基数nums[i]。然后进行内层遍历[ i+1 -- size ]
 *        内层循环中就需要进行比较当前的数nums[j] 和 基数nums[i] 之间的大小关系
 *        找到本轮内层循环中的最小值， 放到最左边。
 *        依次往复，直到遍历到数组的最右端。
 * @param nums
 * @param size
 */
void SelectSort(int nums[], int size){
    /**
     * 在实现每轮排序的时候 ，将未排序部分的数中最小的放到数组的最左边
     */
     for(int i = 0 ; i <size; i++){
         int k  = i;
         //内排序部分，将每轮中最小的部分放到数组的开头
         for (int j = i + 1; j < size; j++) {
             if(nums[k] > nums[j]){
                 k = j;
             }
         }
         swap(nums[i],nums[k]);
     }

}

/**
 * 实现冒泡排序
 * 从后向前进行遍历，以当前 nums[i] 为基数。 进行内循环从 [0 - i]
 * 如果说内层中有某个数nums[j] 比 基数 大， 那么就交换这个数nums[j]  和 基数 nums[i]
 * 如此往复 ，直到基数遍历到初始位置。
 * @param nums 数组
 * @param size 数组大小
 */
void mopoSort(int nums[] , int size){
    //先冒泡出来一个数字， 然后将其和其他的进行比较， 如果大于其那么就交换。然后知道
    for(int i = size -1 ;i > 0 ;i--){
        for (int j = 0; j < i; j++) {
            if (nums[i] < nums[j]){
                swap(nums[i],  nums[j]);
            }
        }
    }
}

/**
 * 插入排序
 *      首先我们假设 基数之前的数已经排序好， 然后以后面的数为基数nums[i] 开始遍历之前的数，看看当前数插入的位置
 *      我们需要将前面的数一一记录 nums[j+1] = nums[j]
 *      直到[基数base < 遍历到的某个数nums[j]  或者 遍历到了最初位置 ]
 *      我们就需要将我们需要插入的基数 插入到当前的位置
 * @param nums 需要排序的数组
 * @param size 数组的大小
 */
void insertSort(int nums[] , int size){
    //需要用到递归
    for (int i = 1; i < size; i++) {
        int base = nums[i];
        int j = i - 1; // 从前一个已经排序好的数开始比较
        cout<<"当前的数为: "<<base <<endl;
        //如果说当前数nums[j] 小于 已经排好的数时，进行交换
        while( j >= 0 && nums[j] > base){
            nums[j+1] = nums[j];    //将当
            j--;
        }
        nums[j+1] = base;
        cout<<"排序后的顺序为: ";
        listNum(nums,size);
        cout <<endl;
    }
}

/**
 * 折半插入排序
 * 折半插入排序相较于直接插入排序是在查找插入位置上做了优化。
 *      1. 首先根据索引找到需要插入的base元素
 *      2. base元素进行索引的区域 [ 0, i-1 ] ,因为插入排序的思想就是假设base元素之前的元素都是已经排序好的。
 *      3. 确定了插入的区域，我们就可以进行优化插入（进行折半）
 *          3.1.  通过while循环，先比较中间元素 和 base 元素的大小，
 *          3.2.  if(base >= nums[mid]) 就缩小查询的范围[ begin, end ] ---将begin改变---> [ mid+1 , end ]
 *          3.3.  if(base < nums[mid]) 就缩小查询的范围[ begin, end ] ---将end改变---> [ begin , mid - 1]
 *      4. 经过上述的操作， 我们就可以得到base的插入位置， 接下来就需要将数组中需要移动的元素整体向后移动。
 *      5. 然后插入到相应的位置。
 * @param nums 数组
 * @param size 数组大小
 */
void BinInsertSort(int nums[], int size){
    for (int i = 1; i < size; ++i) {
        int base = nums[i];
        int begin = 0;
        int end = i-1;
        //实现折半查找插入位置
        while(begin <= end){
            int mid = (begin + end) /2 ;
            if (nums[mid] >= base){
                end = mid - 1;
            }else {
                begin = mid + 1;
            }
        }
        //将元素整体向后移动一位， 给插入的元素腾出位置
        for (int j = i-1; j >= begin ; j--) {
            nums[j+1] = nums[j];
        }
        nums[begin] = base;
    }
}

/**
 * 归并排序
 * 归并排序的思路还是分治思想的实现
 * 首先将元素通过递归的形式 分 ，分到最后两个元素就进行比较， 然后进行排序
 * 最后再通过回溯将排序好的元素进行插入
 * @param nums
 * @param size
 */
void mergeSort(int nums[], int size ){
    divide(nums, 0 , size- 1);
}



//进行递归的划分
void divide(int nums[] ,int left , int right){
    if(left >= right ){
        return;
    }
    int mid = (left + right) /2;
    divide(nums, left, mid);
    divide(nums, mid + 1, right);
    merge(nums, left, mid, right);
}



/**
 * 归并实现
 * todo 注意点: 边界取值问题
 * @param nums 需要排序的数组
 * @param left 数组左边index
 * @param mid 数组中间
 * @param right 数组右边index
 */
void merge(int nums[], int left, int mid, int right){
    int size= right - left + 1;
    int temp[size] ;
    //1.  先定义一个辅助数组， 将原数组的内容全部copy到辅助数组中
    int i = left, j = mid + 1; //左右数组的起始位置index
    int index = 0;
    while(i<= mid && j <= right ){
        //比较左右数组的元素大小， 将较小的那个加入到新数组中
        if (nums[i] < nums[j]){
            temp[index++] = nums[i++];
        }
        else{
            temp[index++] = nums[j++];
        }
    }
    //如果还有左数组 || 右数组 还有元素没有添加进入那就全部导入

    while( i <= mid){
        temp[index++] = nums[i++];
    }

    while( j <= right){
        temp[index++] = nums[j++];
    }

    //然后将临时数组中的元素全部转到原来的数组中

    // 将临时数组中的元素复制回原数组
    for (int p = 0; p < index; p++) {
        nums[left + p] = temp[p];
    }
}