数据结构与算法：交换排序

2023-09-20

字数统计: 740字 | 阅读时长≈ 3分

交换排序

基于比较的排序算法，通过不断交换元素的位置，使得排序的元素达到有序。
主要有冒泡排序和快速排序。

冒泡排序

冒泡排序思路与实现都很简单，通过不断比较两个相邻的元素，如果第一个元素比第二个元素大，则交换两个元素的位置，这样循环一轮下来，最大的元素就浮到了最右边。

同样将数组分为待排区和有序区，实现如下：

void BubbleSort(int* arr, int n) 
{
    for(int i=0;i<n-1;i++){
        for(int j=0;j<n-i-1;j++){
            if(arr[j]>arr[j+1]){
                swap(arr[j],arr[j+1]);
            }
        }
    }
}

优化：使用一个Flag进行标记，初始化为0，如果不发生交换则说明已经有序，可以直接break：

void BubbleSort(int* arr, int n) 
{
    for(int i=0;i<n-1;i++){
        int Flag=0;
        for(int j=0;j<n-i-1;j++){
            if(arr[j]>arr[j+1]){
                Flag=1;
                swap(arr[j],arr[j+1]);
            }
        }
        if(Flag==0){
            break;
        }
    }
}

快速排序

每一遍排序都选一个基准数K，每次都把比K大的数放在K的右边，比K小的数放在K的左边，最后把K放到中间。
随后对K前面的数组和K后面的数组重复上述操作，直到所有数都有序。
由此可知快速排序是基于递归的，递归的终止条件是数组只有一个元素。

模拟：
有数组{3,4,6,1,2,5}
取第一个数3为基准，K=3，定义i、j，i从左开始，j从右开始，从右找到第一个比3小的数2，放在第一个位置，并空出来；i在寻找第一个比3大的数4，放在数组中原先2的位置，变化过程为：
{3,4,6,1,2,5}->{2,4,6,1,2,5}->{2,4,6,1,4,5}
一次类推直到i=j，此时K=3，将K放到中间，并返回K的位置，此时数组为{2,1,3,6,4,5}。
随后进行递归，直到数组中只有一个元素：
{2,1,3,6,4,5}->{2,1}+{6,4,5}->{1,2}+{5,4,6}->{1,2}+{4,5,6},随后进行归并得到{1,2,4,5,6}。

K怎么选：

选择区间的第一个数
选择区间的最后一个数
选择区间的中间数
进行排序时要保证K的选取方式保持一致。

以选择第一个数为K进行排序：

void QuickSort(int* arr, int left, int right)
{
    if(left>=right){
        return;
    }   
    int K=arr[left];
    int i=left;
    int j=right;
    while(left<right){
        while(left<right && arr[right]>K){
            right--;
        }
        if(left<right){
            arr[left]=arr[right];
            left++;
        }

        while(left<right && arr[left]<K){
            left++;
        }
        if(left<right){
            arr[right]=arr[left];
            right--;
        }
    }
    arr[left]=K;

    QuickSort(arr,i,left-1);
    QuickSort(arr,left+1,j);

}

本文作者： KongXinQing
本文链接： https://13114987559.github.io/2023/09/20/note/数据结构与算法-交换排序/
版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！