插入、冒泡、希尔、选择、递归快速、堆排序

文章目录

• • • 1.插入排序
    • 2.冒泡排序
    • 3.希尔排序
    • 4.选择排序
    • 5.快速排序
    • 6.堆排序

1.插入排序

void InsertSort(int* a, int n)
{
    //i的最大下标为n-2,
    for(int i=0;i<n-1;i++)
    {
        //下标为end+1的元素是每次循环需要排序的元素
    	int end=i;
    	int tmp=a[end+1];
    	while(end>=0)
    	{
        	if(tmp<a[end])
        	{
            	a[end+1]=a[end];
            	--end;
        	}
        	else
        	{
            	break;
        	}
    	}
    	a[end+1]=tmp;
    }
}

时间复杂度：O(n^2)

2.冒泡排序

void Swap(int* pa, int* pb)
{
	int tmp = *pa;
	*pa = *pb;
	*pb = tmp;
}

void BubbleSort(int* a, int n)
{
	for (int j = 0; j < n; ++j)
	{
		int exchange = 0;
		// 单趟
		for (int i = 1; i < n-j; ++i)
		{
			if (a[i - 1] > a[i])
			{
				exchange = 1;
				Swap(&a[i - 1], &a[i]);
			}
		}

		if (exchange == 0)
		{
			break;
		}
	}
}

时间复杂度：O(n^2)

3.希尔排序

特点

gap越小，越有序

gap越大，最大多数越在后面，越小的数越在前面，但是越无序

3.1一般希尔排序

void ShellSort(int*a,int n)
{
    for(int j=0;j<gap;j++)
    {
        for(int i=j;i<n-gap;i+=gap)
        {
            //单躺希尔排序
            int i=end;
            int tmp=a[end+gap];
            while(end>=0)
            {
                if(tmp<a[end])
                {
                    a[end+gap]=a[end];
                    end-=gap;
                }
                else
                {
                    break;
                }
            }
            a[end+gap]=tmp;-
        }
    }
}

3.2改进的希尔排序

多组同时进行预排序

void ShellSort(int*a,int n)
{
    int gap=n;
    while(gap>1)
    {
        gap=gap/3+1;
        //多组同时进行预排序
        for(int i=0;i<n-gap;i++)
        {
            int end=i;
            int tmp=a[end+gap];
            while(end>=0)
            {
                if(tmp<a[end])
                {
                    a[end+gap]=a[end];
                    end-=gap;
                }
                else
                {
                    break;
                }
            }
            a[end+gap]=tmp;
        }
    }
}

4.选择排序

void SelectSort(int*a,int n)
{
    //双指针的选择排序
    int left=0,right=n-1;
    while(left<right)
    {
        int mini=left,maxi=left;
        for(int i=left+1;i<=right;i++)
        {
            if(a[i]<a[mini])
            {
                mini=i;
            }
            if(a[i]>a[maxi])
            {
                maxi=i;
            }
            Swap(&a[left],&a[mini]);
            //当目前的最小值的下标恰好是left时
            if(left==mini)
            {
                maxi=mini;
            }
            Swap(&a[right],&a[maxi]);
            left++;
            right--;
        }
    }
}

5.快速排序

算法实现：

​ 左边做key,就右边先走

​ 右边做key,就左边先走

进行单趟排序

//先进行每一趟的排序
int PartSort(int*a,int left,int right)
{
    int key=left;
    while(left<right)
    {
        //右边先走
        while(left<right&&a[right]>=a[key]) right--;
        while(left<right&&a[left]<=a[key]) left++;
        Swap(&a[left],&a[right]);
    }
    Swap(&a[key],&a[left]);
    return left;
}

递归快排

//模板一
void QuickSort(int*a,int begin,int end)
{
    if(begin>=end)
        	return ;
    //返回中间的值
    int key=PartSort(a,begin,end);
    QuickSort(a,0,key-1);
    QuickSort(a,key+1,end-1);
}
//模板二
void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while (i < j)
    {
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j), quick_sort(q, j + 1, r);
}

6.堆排序

步骤一：向下调整法

void AdjustDown(int* a, size_t size, size_t root)
{
    size_t parent=root;
    //假设需要交换的是左孩子
    size_t child=parent*2+1;
    while(child<size)
    {
        //如果右孩子存在且比右孩子小
        if(child+1<size&&a[child+1]<a[child])
        {
            child++;
        }
        if(a[child]>a[parent])
        {
            Swap(&a[child],&a[parent]);
            parent=child;
            child=parent*2+1;
        }
        else
        {
            break;
        }
    }
}

步骤二

void HeapSort(int*a,int n)
{
    //先建堆,从最后一个元素的parent开始，最后一层的结点本来就是堆，所以不用进行排序
    
    //建立大堆
    for(int i=(n-1-1)/2;i>=0;i--)
    {
        //向下调整
       AdjustDown(a,n,i);
    }
    size_t end=n-1;
    while(end>0)
    {
        Swap(&a[0],&a[end]);
        AdjustDown(a,end,0);
        end--;
    }
}