首页 > 其他分享 >【初阶数据结构】11.排序（2）

【初阶数据结构】11.排序（2）

时间：2024-07-31 15:57:53浏览次数：8  
标签：11 arr 初阶 int keyi right 排序 数据结构 left

文章目录

2.3 交换排序

交换排序基本思想：

所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置

交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动

2.3.1 冒泡排序

前面在算法题中我们已经接触过冒泡排序的思路了，冒泡排序是一种最基础的交换排序。之所以叫做冒泡排序，因为每一个元素都可以像小气泡一样，根据自身大小一点一点向数组的一侧移动。

90220543959701b95a30f985f38ce559

代码实现：

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

冒泡排序的特性总结

  1. 时间复杂度：O(N2 )
  2. 空间复杂度：O(1)

2.3.2 快速排序

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

快速排序实现主框架：

//快速排序
void QuickSort(int* a, int left, int right) 
{
    if (left >= right) {
        return;
    }
    //_QuickSort用于按照基准值将区间[left,right)中的元素进行划分
    int meet = _QuickSort(a, left, right);
    QuickSort(a, left, meet - 1);
    QuickSort(a, meet + 1, right);
}

将区间中的元素进行划分的 _QuickSort 方法主要有以下几种实现方式：

2.3.2.1 hoare版本

算法思路 ：

  1. 创建左右指针，确定基准值

  2. right从右向左找出比基准值小的数据，left从左向右找出比基准值大的数据，左右指针数据交换，进入下次循环

问题1：为什么跳出循环后right位置的值一定不大于key？

当 left > right 时，即right走到left的左侧，而left扫描过的数据均不大于key，因此right此时指向的数据一定不大于key

f802ebaaee1af75ab282651dcffa92bf

问题2：为什么left 和 right指定的数据和key值相等时也要交换？

相等的值参与交换确实有一些额外消耗。实际还有各种复杂的场景，假设数组中的数据大量重复时，无法进行有效的分割排序。

a1c57dd3e7292dd607123c05b75540ce

key是基准值

例如：

6 1 2 7 9 3

key指向6，left指向1，right指向3

left从左向右找出比基准值大的数据，right从右向左找出比基准值小的数据，左右指针数据交换，进入下次循环

left指向7，right指向3

交换left和right

left指向的数据7变成数据3，right指向的数据3变成数据7

6 1 2 3 9 7

key指向6，left指向3，right指向7

left从左向右找出比基准值大的数据，right从右向左找出比基准值小的数据，左右指针数据交换，进入下次循环

left指向9，right指向3

此时left>right

left > right的时候，right和基准值key交换

交换key和right的数据

3 1 2 6 9 7

然后返回基准值6

代码实现：

Sort.h

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include<stdlib.h>
#include<time.h>

//打印
void PrintArr(int* arr, int n);
//快速排序
//hoare版本
void QuickSort(int* arr, int left, int right);

Sort.c

#include"Sort.h"

//打印
void PrintArr(int* arr, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}

//交换
void Swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}

//快速排序找基准值
int _QuickSort(int* arr, int left, int right)
{
	int keyi = left;
	++left;

	while (left <= right)//left和right相遇的位置的值比基准值要大
	{
		//right找到比基准值小的
		while (left <= right && arr[right] > arr[keyi])
		{
			right--;//right从右往左找比基准值keyi要小的，当前位置不满足就向前一位
		}
		//left找到比基准值大的
		while (left <= right && arr[left] < arr[keyi])
		{
			left++;//left从左往右找比基准值keyi要大的，当前位置不满足就向后一位
		}
		//right和left互相交换
		//因为left找到比基准值大的，right找到比基准值小的
		//left比right小的时候，自然要交换数据
		if (left <= right)
		{
			Swap(&arr[left++], &arr[right--]);
		}
	}
	//left > right的时候，right和基准值keyi交换
	Swap(&arr[keyi], &arr[right]);

	return right;//返回基准值
}

//快速排序
void QuickSort(int* arr, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	//[left,right]--->找基准值keyi
	int keyi = _QuickSort(arr, left, right);
	//左子序列：[left,keyi-1]
	QuickSort(arr, left, keyi - 1);
	//右子序列：[keyi+1,right]
	QuickSort(arr, keyi + 1, right);
}

test.c

#include"Sort.h"

int main()
{
	int a[] = { 5, 3, 9, 6, 2, 4, 7, 1, 8 };
	int n = sizeof(a) / sizeof(int);
	printf("排序前：");
	PrintArr(a, n);

	QuickSort(a, 0, n - 1);

	printf("排序后：");
	PrintArr(a, n);

	return 0;
}
2.3.2.2 挖坑法

思路：

创建左右指针。首先从右向左找出比基准小的数据，找到后立即放入左边坑中，当前位置变为新的坑，然后从左向右找出比基准大的数据，找到后立即放入右边坑中，当前位置变为新的坑，结束循环后将最开始存储的分界值放入当前的坑中，返回当前坑下标（即分界值下标）

7f127d97b2d93319bb37d19159e3094e

代码：

Sort.h

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include<stdlib.h>
#include<time.h>

//打印
void PrintArr(int* arr, int n);
//快速排序
//挖坑法
void QuickSort(int* arr, int left, int right);

Sort.c

#include"Sort.h"

//打印
void PrintArr(int* arr, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}

//快速排序找基准值
//挖坑法
int _QuickSort2(int* arr, int left, int right)
{
	int hole = left;//找到坑位
	int key = arr[hole];//存储第一个坑位的值

	while (left < right)//left = right就跳出循环
	{
		while (left < right && arr[right] > key)//找到arr[right] < key的right
		{
			--right;
		}
		arr[hole] = arr[right];//填坑
		hole = right;//确定新的坑位

		while (left < right && arr[left] < key)//找到arr[left] > key的left
		{
			++left;
		}
		arr[hole] = arr[left];//填坑
		hole = left;//确定新的坑位
	}
	arr[hole] = key;//最后的坑位放上初始值
	return hole;//返回基准值
}

//快速排序
void QuickSort(int* arr, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	//[left,right]--->找基准值keyi
	int keyi = _QuickSort(arr, left, right);
	//左子序列：[left,keyi-1]
	QuickSort(arr, left, keyi - 1);
	//右子序列：[keyi+1,right]
	QuickSort(arr, keyi + 1, right);
}

test.c

#include"Sort.h"

int main()
{
	int a[] = { 5, 3, 9, 6, 2, 4, 7, 1, 8 };
	int n = sizeof(a) / sizeof(int);
	printf("排序前：");
	PrintArr(a, n);

	QuickSort(a, 0, n - 1);

	printf("排序后：");
	PrintArr(a, n);

	return 0;
}

当然这里会有一点小问题的。比如数据是升序的时候，基准值找起来会有点问题。但因为这里是初阶数据结构，所以先不讨论基准值。后面的高阶数据结构里面会讲三数取中。

2.3.2.3 lomuto前后指针

创建前后指针，从左往右找比基准值小的进行交换，使得小的都排在基准值的左边。

1758c026cc6d45644b6526fe9ac5dd67

思路：

定义两个变量prev和cur

cur指向位置的数据和key值比较

若arr[cur] < arr[keyi]，prev往后走一步并和cur交换

若arr[cur] > arr[keyi]，cur继续往后

arr[cur]越界后，将key里的值和arr[prev]的值互换。

代码：

Sort.h

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include<stdlib.h>
#include<time.h>

//打印
void PrintArr(int* arr, int n);
//快速排序
//lomuto前后指针法
void QuickSort(int* arr, int left, int right);

Sort.c

#include"Sort.h"

//打印
void PrintArr(int* arr, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}

//交换
void Swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}

//快速排序找基准值
//lomuto前后指针法
int _QuickSort3(int* arr, int left, int right)
{
	int prev = left, cur = left + 1;
	int keyi = left;

	while (cur <= right)//cur > right就说明越界了
	{
		if (arr[cur] < arr[keyi] && ++prev != cur)//若arr[cur] < arr[keyi]，prev往后走一步并和cur交换
		{
			Swap(&arr[cur], &arr[prev]);
		}
		cur++;//若arr[cur] > arr[keyi]，cur继续往后
	}
	Swap(&arr[keyi], &arr[prev]);//arr[cur]越界后，将key里的值和arr[prev]的值互换。

	return prev;//返回基准值
}

//快速排序
void QuickSort(int* arr, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	//[left,right]--->找基准值keyi
	int keyi = _QuickSort(arr, left, right);
	//左子序列：[left,keyi-1]
	QuickSort(arr, left, keyi - 1);
	//右子序列：[keyi+1,right]
	QuickSort(arr, keyi + 1, right);
}

test.c

#include"Sort.h"

int main()
{
	int a[] = { 5, 3, 9, 6, 2, 4, 7, 1, 8 };
	int n = sizeof(a) / sizeof(int);
	printf("排序前：");
	PrintArr(a, n);

	QuickSort(a, 0, n - 1);

	printf("排序后：");
	PrintArr(a, n);

	return 0;
}

快速排序特性总结：

  1. 时间复杂度：O(nlogn)
  2. 空间复杂度：O(logn)
2.3.2.4 非递归版本

非递归版本的快速排序需要借助数据结构：栈

思路：

假设我们初始要排序的数是：5 3 9 6 2 4

经过一轮快速排序后，找到的基准值是6，也就是keyi=3

通过一轮快速排序后，接下来要排序的数是2 3 4 5 6 9

如果left=0，right=5，keyi=3

左区间：[left,keyi-1] [0,2]

右区间：[keyi+1,right] [4,5]

先把右区间的right：5入栈，然后把右区间的left：4入栈

然后把左区间的right：2入栈，然后把左区间的left：0入栈

此时栈里面是：0 2 4 5

然后出栈两次，取到left=0，right=2

我们对下标为0-2的数找基准值

找到基准值keyi=0

此时left=0，right=2，keyi=1

左区间：[left,keyi-1] [0,-1] 非有效区间，不入栈

右区间：[keyi+1,right] [1,2]

先把右区间的right：2入栈，然后把右区间的left：1入栈

此时栈里面是：1 2 4 5

然后出栈两次，取到left=1，right=2

我们对下标为1-2的数找基准值

找到基准值keyi=1

此时left=1，right=2，keyi=1

左区间：[left,keyi-1] [1,0] 非有效区间，不入栈

右区间：[keyi+1,right] [2,2] 非有效区间，不入栈

此时栈里面是：4 5

然后出栈两次，取到left=4，right=5

我们对下标为4-5的数找基准值

找到基准值keyi=4

此时left=4，right=5，keyi=4

左区间：[left,keyi-1] [4,3] 非有效区间，不入栈

右区间：[keyi+1,right] [5,5] 非有效区间，不入栈

此时排完序了，是2 3 4 5 6 9

我们销毁函数栈。

代码实现：

Sort.h

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include<stdlib.h>
#include<time.h>
#include <stdbool.h>
#include <assert.h>

//打印
void PrintArr(int* arr, int n);
//非递归版本快排
//--借助数据结构--栈
void QuickSortNonR(int* arr, int left, int right);

Sort.c

#include"Sort.h"

//打印
void PrintArr(int* arr, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}

//定义栈的结构
typedef int STDataType;
typedef struct Stack
{
	STDataType* arr;
	int capacity;     //栈的空间大小
	int top;          //栈顶
}ST;

//栈的初始化
void STInit(ST* ps)
{
	assert(ps);
	ps->arr = NULL;
	ps->capacity = ps->top = 0;
}

//栈顶---入数据，出数据
//入数据
void StackPush(ST* ps, STDataType x)
{
	assert(ps);

	//1.判断空间是否足够
	if (ps->capacity == ps->top)
	{
		int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("realloc fail!");
			exit(1);
		}
		ps->arr = tmp;
		ps->capacity = newCapacity;
	}
	//空间足够
	ps->arr[ps->top++] = x;
}

//判断栈是否为空
bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}

//栈顶出数据
void StackPop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));

	--ps->top;
}

//取栈顶元素
STDataType StackTop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));

	return ps->arr[ps->top - 1];
}

//栈的销毁
void STDestroy(ST* ps)
{
	assert(ps);
	if (ps->arr)
		free(ps->arr);
	ps->arr = NULL;
	ps->top = ps->capacity = 0;
}

//非递归版本快排
//--借助数据结构--栈
void QuickSortNonR(int* arr, int left, int right)
{
	ST st;//创建栈
	STInit(&st);//栈的初始化
	StackPush(&st, right);//栈顶入数据
	StackPush(&st, left);//栈顶入数据

	while (!StackEmpty(&st))//栈不为空就进入循环
	{
		//取栈顶元素---取两次
		int begin = StackTop(&st);
		StackPop(&st);//栈顶出数据

		int end = StackTop(&st);
		StackPop(&st);//栈顶出数据

		//[begin,end]---找基准值
		//双指针法
		int prev = begin;
		int cur = begin + 1;
		int keyi = begin;

		while (cur <= end)
		{
			if (arr[cur] < arr[keyi] && ++prev != cur)//这里<和<=一样
			{
				Swap(&arr[cur], &arr[prev]);
			}
			cur++;
		}
		Swap(&arr[keyi], &arr[prev]);//上面循环结束说明cur越界了

		keyi = prev;
		//根据基准值keyi划分左右区间
		//左区间：[begin,keyi-1]
		//右区间：[keyi+1,end]

		if (keyi + 1 < end)
		{
			StackPush(&st, end);//右区间入栈
			StackPush(&st, keyi + 1);//左区间入栈
		}
		if (keyi - 1 > begin)
		{
			StackPush(&st, keyi - 1);//右区间入栈
			StackPush(&st, begin);//左区间入栈
		}
	}

	STDestroy(&st);//销毁栈
}

test.c

#include"Sort.h"

int main()
{
	int a[] = { 5, 3, 9, 6, 2, 4, 7, 1, 8 };
	int n = sizeof(a) / sizeof(int);
	printf("排序前：");
	PrintArr(a, n);

	QuickSortNonR(a, 0, n - 1);

	printf("排序后：");
	PrintArr(a, n);

	return 0;
}

2.4 归并排序

归并排序算法思想：

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 归并排序核心步骤：

45fedca89a7046dfaa8bd24a4bb1962d

思路：

数据：10 6 7 1 3 9 4（7个元素，下标0-6）

定义left，right，mid三个变量

left指向下标0的元素

right指向下标6的元素

mid=(left+right)/2

[left,mid]：10 6 7 1

[mid+1,right]：3 9 4

然后可以继续像上面这样分，直到全部分成一个一个的数据。

递归的话也是递归到这个时候结束，然后往上返回。

12653da879b1489b83c1bee59b5dfe19

那么，对于10 6这两个数字组成的数组，我们怎么把他排序成6 10呢？

left指向下标0的元素

right指向下标1的元素

mid=(left+right)/2=0

[left,mid]：[0,0] 10

[mid+1,right]：[1,1] 6

其他几个数据也一样

然后我们新创建一个数组来存放这些数：6 10， 1 7， 3 9， 4

然后往上返回。

ff57a163facec37b1c08ffb00046f857

然后我们新创建一个数组来存放这些数：6 10 1 7， 3 9 4

然后往上返回。

4815ea9722df416e7c9556c5d54bcd0e

然后把tmp中的数据拷贝回arr中

销毁tmp

代码：

Sort.h

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include<stdlib.h>
#include<time.h>
#include <stdbool.h>
#include <assert.h>

//打印
void PrintArr(int* arr, int n);
//归并排序
void MergeSort(int* arr, int n);

Sort.c

#include"Sort.h"

//打印
void PrintArr(int* arr, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}

//归并排序
void _MergeSort(int* arr, int left, int right, int* tmp)
{
	if (left >= right)//分解到只有一个数据的时候就结束了
	{
		return;
	}
	int mid = (left + right) / 2;//中间下标
	//[left,mid] [mid+1,right]
	//不断二分
	_MergeSort(arr, left, mid, tmp);
	_MergeSort(arr, mid + 1, right, tmp);


	//合并
	//[left,mid] [mid+1,right]
	//表示两个区间
	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;
	int index = begin1;//定义tmp数组的下标

	while (begin1 <= end1 && begin2 <= end2)
	{
		if (arr[begin1] < arr[begin2])//比较arr[begin1] 和 arr[begin2]的大小
		{
			tmp[index++] = arr[begin1++];//先往tmp里面插入小的
		}
		else {
			tmp[index++] = arr[begin2++];//然后往tmp里面插入大的
		}
	}
	//跳出循环：要么begin1越界  要么begin2越界
	while (begin1 <= end1)//begin2越界，begin1没有越界
	{
		tmp[index++] = arr[begin1++];//继续插入
	}
	while (begin2 <= end2)//begin1越界，begin2没有越界
	{
		tmp[index++] = arr[begin2++];
	}

	//[left,mid] [mid+1,right]
	//把tmp中的数据拷贝回arr中
	for (int i = left; i <= right; i++)
	{
		arr[i] = tmp[i];
	}
}

void MergeSort(int* arr, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);//合并的放在新创建的新数组里，大小是原来数组的空间

	_MergeSort(arr, 0, n - 1, tmp);

	free(tmp);//使用完了要释放掉空间
}

test.c

#include"Sort.h"

int main()
{
	int a[] = { 5, 3, 9, 6, 2, 4, 7, 1, 8 };
	int n = sizeof(a) / sizeof(int);
	printf("排序前：");
	PrintArr(a, n);

	MergeSort(a, n);

	printf("排序后：");
	PrintArr(a, n);


	TestOP();

	return 0;
}

归并排序特性总结：

  1. 时间复杂度：O(nlogn)
  2. 空间复杂度：O(n)

2.5 测试代码：排序性能对比

// 测试排序的性能对比
void TestOP() 
{ 
    srand(time(0)); 
    const int N = 100000; 
    int* a1 = (int*)malloc(sizeof(int)*N); 
    int* a2 = (int*)malloc(sizeof(int)*N); 
    int* a3 = (int*)malloc(sizeof(int)*N); 
    int* a4 = (int*)malloc(sizeof(int)*N); 
    int* a5 = (int*)malloc(sizeof(int)*N); 
    int* a6 = (int*)malloc(sizeof(int)*N); 
    int* a7 = (int*)malloc(sizeof(int)*N); 
    for (int i = 0; i < N; ++i) 
    { 
        a1[i] = rand(); 
        a2[i] = a1[i]; 
        a3[i] = a1[i]; 
        a4[i] = a1[i]; 
        a5[i] = a1[i]; 
        a6[i] = a1[i];
        a7[i] = a1[i]; 
    } 
    int begin1 = clock(); 
    InsertSort(a1, N); 
    int end1 = clock(); 

    int begin2 = clock(); 
    ShellSort(a2, N); 
    int end2 = clock(); 

    int begin3 = clock(); 
    SelectSort(a3, N); 
    int end3 = clock(); 

    int begin4 = clock(); 
    HeapSort(a4, N); 
    int end4 = clock(); 

    int begin5 = clock(); 
    QuickSort(a5, 0, N-1); 
    int end5 = clock(); 

    int begin6 = clock(); 
    MergeSort(a6, N); 
    int end6 = clock(); 

    int begin7 = clock(); 
    BubbleSort(a7, N); 
    int end7 = clock();

    printf("InsertSort:%d\n", end1 - begin1); 
    printf("ShellSort:%d\n", end2 - begin2);
    printf("SelectSort:%d\n", end3 - begin3); 
    printf("HeapSort:%d\n", end4 - begin4); 
    printf("QuickSort:%d\n", end5 - begin5); 
    printf("MergeSort:%d\n", end6 - begin6); 
    printf("BubbleSort:%d\n", end7 - begin7); 

    free(a1); 
    free(a2); 
    free(a3); 
    free(a4); 
    free(a5); 
    free(a6); 
    free(a7); 
}

对于上面程序的测试结果：（单位：ms）

InsertSort:3816
ShellSort:13
SelectSort:4253
HeapSort:15
QuickSort:9
MergeSort:12
BubbleSort:22812

2.6 非比较排序

2.6.1 计数排序

计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。 操作步骤：

  1. 统计相同元素出现次数

  2. 根据统计的结果将序列回收到原来的序列中

思路：

例如：{6，1，2，9，4，2，4，1，4}共9个数

  1. 统计相同元素出现次数

6出现1次，1出现2次，2出现2次，9出现1次，4出现3次

  1. 根据统计的结果将序列回收到原来的序列中

fca1a4c8a3578dc560a5c70715dbf4f6

定义一个i来遍历，i表示数组内元素

i先到0的位置，里面没有数据，不打印

然后到1的位置，里面有2，打印2次

依次类推

最后打印结果：1 1 2 2 4 4 4 6 9

新数组的大小怎么确定？

利用原数组中最大的值来确定。创建max+1个空间的数组。

但这就会出现问题：比如有负数怎么办？比较{3, 4, 10000}呢?

如果把负数变成正数，取绝对值呢？也不行。因为正负数绝对值一样的情况下无法区分正负数。

那如果我们把负数统一加一个正数，让他变成整数呢？

我们可以让count=max-min+1

对于{-5，-5，9，5，1}

count=9-（-5）+1=15

创建数组，数组大小为15，下标为0-14

-5放在数组下标为0的位置中，这个位置元素为2

依此类推，下标-5就是原来的元素，这些元素和下标形成了映射关系。

fa7b858e7ef858bc2913b63473724b91

代码：

Sort.h

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include<stdlib.h>
#include<time.h>
#include <assert.h>
#include <stdbool.h>
#include <memory.h>

//打印
void PrintArr(int* arr, int n);

//计数排序
void CountSort(int* arr, int n);

Sort.c

#include "Sort.h"

//打印
void PrintArr(int* arr, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}

//计数排序
void CountSort(int* arr, int n)
{
	//根据最大值最小值确定数组大小
	int max = arr[0], min = arr[0];
	for (int i = 1; i < n; i++)
	{
		if (arr[i] > max)
		{
			max = arr[i];
		}
		if (arr[i] < min)
		{
			min = arr[i];
		}
	}

	int range = max - min + 1;//确定数组元素个数
	int* count = (int*)malloc(sizeof(int) * range);//创建数组
	//判断不为空
	if (count == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	//初始化count数组中所有的数据为0
	memset(count, 0, range * sizeof(int));//count的大小是range

	//例如{100，101，109，105，101，105}
	//min = 100，arr[i] - min就是count里面的下标
	//统计数组中每个数据出现的次数
	for (int i = 0; i < n; i++)
	{
		count[arr[i] - min]++;//这里的++是为了把次数放进去
	}

	//取count中的数据，往arr中放
	int index = 0;
	for (int i = 0; i < range; i++)
	{
		while (count[i]--)//这里是为了把上面count对应次数给传进arr
		{
			arr[index++] = i + min;//表示arr数组的下标从0开始，存放数据
		}
	}
}

test.c

#include "Sort.h"

int main()
{
	int a[] = { 5, 3, 9, 6, 2, 4, 7, 1, 8 };
	int n = sizeof(a) / sizeof(int);
	printf("排序前：");
	PrintArr(a, n);

    CountSort(a, n);

	printf("排序后：");
	PrintArr(a, n);

	return 0;
}

计数排序的特性：

计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。 而且只能适用于整数排序，无法对小数排序。

时间复杂度：O(N + range)

空间复杂度：O(range)

稳定性：稳定

3.排序算法复杂度及稳定性分析

稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

比如：6 2 4 9 1 2

排序后：1 2 2 4 6 9

一开始有两个2，一个在前面，一个在后面。

排序后也有两个2，一个在前面，一个在后面。

如果排序后前面的2还是在后面的2的前面，就称相对次序保持不变。称这种排序算法是稳定的；否则称为不稳定的。

e7b8b43a4d13a606ecdad3ae8021da6a

a07c89bf10f6b75bae782786b19431ff

稳定性验证案例

  1. 直接选择排序：5 8 5 2 9

  2. 希尔排序：5 8 2 5 9

  3. 堆排序：2 2 2 2

  4. 快速排序：5 3 3 4 3 8 9 10 11

标签：11,arr,初阶,int,keyi,right,排序,数据结构,left
From： https://blog.csdn.net/hlyd520/article/details/140825265

相关文章

  • 微信电脑版v3.9.11.17 防撤回版 多开版
    版本特色：1、看到对方撤回的消息2、多账号可正常登录修改原理，如下图：使用说明：解压后，双击start.bat来运行软件下载地址：Wechat防撤回版v3.9解压密码：helloh下载时可能会有广告，忽略，等下载结束即可部分杀软会因该版本软件未购买签名证书（如下图）而报毒，可通过加入排除项或者信......
  • SOMEIPSRV_RPC_11: 字段的设定器和有效载荷
    测试目的：验证字段的setter方法是否按照规范要求，通过请求/响应调用实现，其中请求消息的负载包含期望的字段值，响应消息的负载包含已设置到字段的值。描述本测试用例旨在验证DUT（DeviceUnderTest，被测试设备）在接收到字段setter方法的请求时，是否能够正确地在响应消息中返回设......
  • 数据结构之八大排序（上）
    找往期文章包括但不限于本期文章中不懂的知识点：个人主页：我要学编程(ಥ_ಥ)-CSDN博客所属专栏：数据结构（Java版） 目录排序的相关介绍直接插入排序 希尔排序（缩小增量排序）选择排序堆排序冒泡排序 排序的相关介绍排序的概念：所谓排序，就是使一串记录，按照其中的某个或......
  • windows11解决visual c++6.0 打开提示不兼容弹窗问题
    在Windows11系统中，打开VisualC++6.0编辑器，会弹出不兼容弹窗，如图所示下面将给出解决办法，实测有效。步骤1：重命名MSDEV.EXE文件 步骤2：修改“兼容模式”配置 步骤3：修改“目标”输入框内容 步骤4：重新启动软件 ......
  • C++初阶大总结
    目录一.命名空间1.命名空间定义2.命名空间使用二.C++输入&输出三.缺省参数四.函数重载五.引用1.常引用2.传值、传引用效率比较3.引用和指针的区别4.引用和指针的不同点:小知识点:六.内联函数七.auto关键字(C++11)1.auto的使用细则八.基于范围的for循环(C++11)......
  • 瑞士ABB苏黎世张力控制器系统PFEA113-65订货号3BSE028144R65
    光学编码器光学编码器信号链元件与磁编码器（AMR）部分介绍的元件几乎相同。但是，为了支持高的编码器分辨率，建议使用AD77602．5MSPS、24位、100dBΣ－ΔADC。它融合了宽输入带宽、高速特性和Σ－Δ转换技术的优势，2．5MSPS时信噪比（SNR）可达100dB，因此非常适合高速数据采集应用。旋变（耦......
  • 瑞士ABB苏黎世张力控制器PFEA112-20
    其特点是控制电路结构简单、成本较低，机械特性硬度也较好，能够满足一般传动的平滑调速要求，已在产业的各个领域得到广泛应用。但是，这种控制方式在低频时，由于输出电压较低，转矩受定子电阻压降的影响比较显著，使输出大转矩减小。另外，其机械特性终究没有直流电动机硬，动态转矩能力和静态......
  • 【数据结构】之线段树理解与基础模板
    什么是线段树线段树是一种通过类似二分来实现的一种二叉树结构，方便区间的修改与性质的查询，是一种非常节约时间的数据结构。为什么使用线段树比如我们给你NNN......
  • Win10/Win11安全中心无法打开解决方式
    按住win键+x打开powershell管理员模式然后输入以下代码sfc/SCANNOW1.等待扫描完成Dism/Online/Cleanup-Image/ScanHealth2.等待进度走完Dism/Online/Cleanup-Image/CheckHealth3.出现未检测到组件损坏，继续下一个命令操作DISM/Online/Cleanup-image/Rest......
  • H3C SecPath 防火墙产品 典型配置案例集(V7)(RXX60 EXX60 E1185)-6W600
    H3CSecPathF1000系列防火墙https://www.h3c.com/cn/Service/Document_Software/Document_Center/IP_Security/FW_VPN/F10X0/?CHID=188680&v=612H3CSecPath防火墙产品典型配置案例集(V7)(RXX60EXX60E1185)-6W600https://www.h3c.com/cn/pub/Document_Center/2023/08/Web......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99