当前位置：首页 > article >正文

交换排序与快速排序

article 2025/1/24 22:52:13

交换排序

基本思想: 所谓交换，就是根据序列中元素值进行比较，根据比较结果对两个数据进行位置的相互交换序列中的位置，交换特点：将键值大的元素向序列尾部移动或将键值小的元素向序列的前部移动。

交换排序之冒泡排序

冒泡排序的代码实现:

public static void swap(int [] arr , int sum1 , int sum2){
    int tmp = arr[sum1];
    arr[sum1] = arr[sum2];
    arr[sum2] = tmp;
}
public static void BubbleSort(int [] arr){

    for (int i = 0; i < arr.length; i++) {
        boolean count = false;
        for (int j = 0; j <arr.length - i -1; j++) {
            if (arr [j] > arr[j+1]){
                swap(arr,j , j+1);
                count =true;
            }
        }
        if (!count){
            break;
        }
    }
}

冒泡排序的特点总结：

1. 冒泡排序是一种非常容易理解的排序

2. 时间复杂度：O(N^2)

3. 空间复杂度：O(1)

4. 稳定性：稳定

快速排序

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有

元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

Hoare版实现

实现思路：

1、选出一个key，一般是最左边或是最右边的。

2、定义一个begin和一个end，begin从左向右走，end从右向左走。（需要注意的是：若选择最左边的数据作为key，则需要end先走；若选择最右边的数据作为key，则需要bengin先走）。

3、在走的过程中，若end遇到小于key的数，则停下，begin开始走，直到begin遇到一个大于key的数时，将begin和right的内容交换，end再次开始走，如此进行下去，直到begin和end最终相遇，此时将相遇点的内容与key交换即可。（选取最左边的值作为key）

4.此时key的左边都是小于key的数，key的右边都是大于key的数

5.将key的左序列和右序列再次进行这种单趟排序，如此反复操作下去，直到左右序列只有一个数据，或是左右序列不存在时，便停止操作，此时此部分已有序

代码实现：

public static void swap(int [] arr , int sum1, int sum2){
    int tmp = arr[sum1];
    arr[sum1] = arr[sum2];
    arr[sum2] = tmp;
}
public static void HoareSort(int [] arr , int left , int right){
    int l = left;
    int r = right;
    int prev = arr[left];
    while (l < r){
        while (l < r && prev <= arr[r]){
            r--;
        }
        while (l < r && prev >= arr[l]){
            l++;
        }
        swap(arr,r,l);
    }
    swap(arr , left , l);
    if (left != l) {
        HoareSort(arr, left, l-1);
    }
    if (l != right) {
        HoareSort(arr, l+1, right);
    }
}

挖坑法实现

挖坑法思路：

1.首先创建临时变量key存放第一个元素，形成坑位。

2.R向左移动当遇到比key小的值，将R的值存放到L坑位后，R形成坑位。

3.L向左移动当到比key大的值，将L的元素值存放到R坑位,L形成坑位。

4.后续操作与hoare版本相同，不多讲解。

挖坑法代码实现

public static void quickSort(int arr[] ,int start , int end){
    if (start >= end){
        return;
    }
    int prev = arr[start];
    int left = start;
    int right = end;
    while (start < end){
        while (start < end && prev <= arr[end]){
            end--;
        }
        arr[start] = arr[end];
        while (start < end && prev >= arr[start]){
            start++;
        }
        arr[end] = arr[start];
    }
    arr[end] = prev;
    quickSort(arr,end +1, right );
    quickSort(arr,left,end-1);
}