博客

六大排序算法C++实现

六大排序包括，冒泡(附加冒泡排序的改进)、选择、插入、堆排序、快排、归并排序，这些排序的定义和优劣这里不赘述，大家可自行查阅其他资料或博客，这里给出他们的C++实现

1、冒泡排序

/*普通冒泡,从未排序的第一个元素开始，
一次和之后的未排序元素比较，若比之后的大，
则交换，这样完成最大的元素冒泡到最后，故称为冒泡
时间复杂度O（n*n），空间复杂度O（1）*/
void maopao(vector<int> &arr)
{
    for(int i = 0;i < arr.size();i++)
    {
        for(int j = 0 ;j < arr.size()-1-i;j++)
        {
            if(arr[j] > arr[j+1])
            {
                int t = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = t;
            }
        }
    }
}

冒泡排序改进

//冒泡改进，如果某一次遍历没有发生一次交换，则说明有序，不用继续遍历
void maopao2(vector<int> &arr)
{
    bool flag = true;
    int i = 0;
    while(flag)
    {
        flag = false;
        for(int j = 0 ;j < arr.size()-1-i;j++)
        {
            if(arr[j] > arr[j+1])
            {
                int t = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = t;
                flag = true;
            }
        }
        i++;
    }

}

2、选择排序

/*选择排序，每一次从未排序元素中选择最小的元素，采用记下标的方式记录，
比当前小，则记下下标，最后与最前面的未排序元素交换，称为选择
时间复杂度O(n*n),空间复杂度O(1)*/
void ChooseSort(vector<int> &arr)
{
    for(int i = 0;i < arr.size();i++)
    {
        int temp = i;
        for(int j = i+1;j < arr.size();j++)
        {
            if(arr[j] < arr[temp])
                temp = j;
        }
        if(i != temp)
        {
            int t = arr[temp];
            arr[temp] = arr[i];
            arr[i] = t;
        }
    }
}

3、插入排序

/*插入排序，降序：选取元素依次与之前的有序比较，比之大，则将元素往后移动，直到找到比之小的元素或者到头
，将该元素插入即可*/
void InsertSort(vector<int> &arr)
{
    for(int i = 1;i < arr.size();i++)
    {
        int j = i;
        int temp = arr[i];
        while(j-1 >= 0 && temp < arr[j-1])
        {
            arr[j] = arr[j-1];
            j--;
        }
        arr[j] = temp;
    }
    return;
}

4、堆排序

/*堆排序，模拟二叉树，对于每个父亲节点i，2*i+1为左儿子，2*i+2为右儿子，调整堆时，需要以父亲节点的身份调整
有2*i+1<=n-1(身为父亲至少有一个左儿子，且左儿子在此数组内)*/
void adjHeap(vector<int> &arr,int i,int n)//小根堆
{
    if(i <= n/2 - 1)
    {
        int j = 2*i+1;
        if(j + 1 <= n - 1 && arr[j+1] < arr[j])
            j++;//若有右儿子，选取两者较小的一个
        if(arr[j] < arr[i])//儿子比父亲小
        {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            adjHeap(arr,j,n);
        }
    }
    return;
}
void HeapSort(vector<int> &arr,int n)
{
    for(int i = n/2 - 1;i >=0;i--)//从最后的父节点开始调整建立堆
    {
        adjHeap(arr,i,n);
    }

    for(int i = n-1;i > 0;i--)//每次将最小的与后面的元素交换，再从跟开始调整
    {
        int temp = arr[i];
        arr[i] = arr[0];
        arr[0] = temp;
        adjHeap(arr,0,i);
    }
    return;
}

5、快速排序

/*快排*/
void QuickSort(vector<int> &arr,int left,int right)
{
    if(left >= right)
        return;
    int oldleft = left;
    int oldright = right;
    int pivot = arr[left];
    while(left < right)//越界一定研严格小于！
    {
        while(left < right && arr[right] >= pivot)//防止相等元素无限循环，加上=号，只选择严格小于
            right--;
        arr[left] = arr[right];
        while(left < right && arr[left] <= pivot)
            left++;
        arr[right] = arr[left];
    }
    arr[left] = pivot;
    QuickSort(arr,oldleft,left-1);
    QuickSort(arr,left+1,oldright);
    return;
}

6、归并排序

/*归并排序*/
void Merge(vector<int> &arr,int left,int mid,int right)
{
    if(left >= right)
        return;
    int i = left;
    int j = mid + 1;
    int k = left;
    vector<int> temp(arr.size(),0);
    while(i <= mid && j <= right)
    {
        if(arr[i] < arr[j])
            temp[k++] = arr[i++];
        else
        {
            temp[k++] = arr[j++];
        }
    }
    while(i <= mid)
        temp[k++] = arr[i++];
    while(j <= right)
        temp[k++] = arr[j++];
    for(int i = left;i <= right;i++)
        arr[i] = temp[i];
}

void MergeSort(vector<int> &arr,int left,int right)
{
    if(left >= right)
        return;
    else
    {
        int mid = (left+right)/2;
        MergeSort(arr,left,mid);
        MergeSort(arr,mid+1,right);
        Merge(arr,left,mid,right);
    }
    return;
}