[数据结构与算法]C++排序算法

01冒泡排序

void maopao(int* pt,int n)
{
	for (int i = n - 1; i > 0; i--)//找出第i大（小）的数
		for (int j = 0; j < i; j++)//在未排序数中依次比较相邻的数，将大的放后面，                      
			if (pt[j] > pt[j + 1])//这样遍历下来最后面的就是未排序数最大（小）的数
			{
				int temp = pt[j];
				pt[j] = pt[j + 1];
				pt[j + 1] = temp;
			}
	for (int i = 0; i < n; i++)
		cout << pt[i] << " ";
}

02插入排序

void charu(int* pt, int n)
{
	for (int i = 1; i < n; i++)
		//将数组分为两部分，每次大循坏给前一部分数量+1.给后一部分数量-1
		//每次小循环将后一部分的第一个元素A从后往前依次与前一部分的元素比较，若是从小到大排列，
		//当A比被比较元素小时则交换
		for (int j = i; j > 0; j--)
		{
			if (pt[j] < pt[j - 1])
			{
				int temp = pt[j - 1];
				pt[j - 1] = pt[j];
				pt[j] = temp;
			}
		}
	for (int i = 0; i < n; i++)
		cout << pt[i] << " ";
}

03选择排序

void xuanze(int* pt, int n)
{
	int tem;
	for (int i = 0; i < n; i++)
	{
		int min = pt[i];
		int j = i;
		int k= i;
		for (; j < n; j++)//找到最小元素下标k
			if (min > pt[j])
			{
				min = pt[j]; k = j;
			}
		tem = pt[i];
		pt[i] = pt[k];
		pt[k] = tem;//最小元素与头部元素交换位置
	}
	for(int i=0;i<n;i++)
		cout << pt[i]<<" ";
}

04希尔排序

void xier(int* pt, int n)
{
	int* ptem=new int[n];
	for (int gap = n / 2; gap >= 1; gap = gap / 2)//进行log2n次分组
	{
		for (int i = 0; i < gap; i++)//整个数组被分为gap个小组,进行gap次插入排序
		{
			for (int i = 0; i < n / gap; i++)//每个小组有n/gap个元素
				ptem[i] = pt[i * gap];//临时创建一个数组来存放排序好的元素
			charutem(ptem, n / gap);//对n/gap个元素插入排序
			for (int i = 0; i < n / gap; i++)
				pt[i * gap] = ptem[i];//将排好序的元素按照对应位置放回原数组
		}
	}
	for (int i = 0; i < n; i++)
		cout << pt[i] << " ";
}

05快速排序

void kuaisu(int* pt, int start, int end,int n)
{
	if (start >= end)![请添加图片描述](https://img-blog.csdnimg.cn/043e754747444f6091e3cb8d0fd71a34.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNTY3NjA3,size_16,color_FFFFFF,t_70)

	return;
	int p1 = start;
	int p2 = end;
	int piv = pt[p1];
		while(p1<p2)
		{
			while (p1 < p2 && pt[p2] >= piv)
			{
				p2--;
			}
		  pt[p1] = pt[p2];
		  while (p1 < p2 && pt[p1] <= piv)
		  {
			  p1++;
		  }
		  pt[p2] = pt[p1];
		}
		pt[p1] = piv;
		kuaisu(pt, start, p1 -1,n);
		kuaisu(pt, p1 + 1, end,n);
}

06归并排序

void merge(int arr[], int l, int q, int r) {
    int n = r - l + 1;//临时数组存合并后的有序序列
    int* tmp = new int[n];
    int i = 0;
    int left = l;
    int right = q + 1;
    while (left <= q && right <= r)
        tmp[i++] = arr[left] <= arr[right] ? arr[left++] : arr[right++];
    while (left <= q)
        tmp[i++] = arr[left++];
    while (right <= r)
        tmp[i++] = arr[right++];
    for (int j = 0; j < n; ++j)
        arr[l + j] = tmp[j];
    delete[] tmp;//删掉堆区的内存
}

void mergesort(int arr[], int l, int r) {
    if (l == r)
        return;  //递归基是让数组中的每个数单独成为长度为1的区间
    int q = (l + r) / 2;
    mergesort(arr, l, q);
    mergesort(arr, q + 1, r);
    merge(arr, l, q, r);
}