09-排序1 排序（C）

这一节，测试各类排序算法的运行速度（没有基数排序（桶）

其实在实际学习中，还是有意义的

给定 n 个（长整型范围内的）整数，要求输出从小到大排序后的结果。

本题旨在测试各种不同的排序算法在各种数据情况下的表现。各组测试数据特点如下：

  • 数据1：只有1个元素；
  • 数据2：11个不相同的整数，测试基本正确性；
  • 数据3：10^{3}个随机整数；
  • 数据4：10^{4}个随机整数；
  • 数据5：10^{5}个随机整数；
  • 数据6：10^{5}个顺序整数；
  • 数据7：10^{5}个逆序整数；
  • 数据8：10^{5}个基本有序的整数；
  • 数据9：10^{5}个随机正整数，每个数字不超过1000。

    输入格式:

    输入第一行给出正整数 n（≤105），随后一行给出 n 个（长整型范围内的）整数，其间以空格分隔。

    输出格式:

    在一行中输出从小到大排序后的结果，数字间以 1 个空格分隔，行末不得有多余空格。

    输入样例:

    11
4 981 10 -17 0 -20 29 50 8 43 -5

    输出样例:

    -20 -17 -5 0 4 8 10 29 43 50 981

 

 //冒泡排序

//冒泡排序
void Bubble_Sort(int *a, int Num)
{
	int Temp, i, j;
	int flag;
	for(i = 0; i < Num; i++){
		flag = 0;
		for(j = 0; j < Num - 1; j++){
			if(a[j] > a[j + 1]){
				Temp = a[j];
				a[j] = a[j+1];
				a[j+1] = Temp;
				flag = 1;
			}
		}
		if(!flag){
			break;
		}
	}	
}
测试点提示内存(KB)用时(ms)结果得分
03522

答案正确

1 / 1
13322

答案正确

10 / 10
23563

答案正确

2 / 2
3276192

答案正确

2 / 2
46883000

运行超时

0 / 2
5120017

答案正确

2 / 2
66643000

运行超时

0 / 2
71296432

答案正确

2 / 2
86683000

运行超时

0 / 2

插入排序

void Insert_Sort(int *a, int Num)
{
	int i, j;
	int Temp;
	for(i = 1; i < Num; i++){
		Temp = a[i];
		for(j = i; j > 0 && a[j-1] > Temp; j--){
			a[j] = a[j-1];
		}
		a[j] = Temp;
	}
}
测试点提示内存(KB)用时(ms)结果得分
03601

答案正确

1 / 1
11761

答案正确

10 / 10
23562

答案正确

2 / 2
342416

答案正确

2 / 2
411441254

答案正确

2 / 2
5120017

答案正确

2 / 2
611762493

答案正确

2 / 2
7120829

答案正确

2 / 2
810481260

答案正确

2 / 2

 希尔排序_普通版

void Shell_Sort(int *a, int Num)
{
	int D, P, i;
	int Temp;
	for(D = Num / 2; D > 0; D /= 2){
		for(P = D; P < Num; P++){
			Temp = a[P];
			for(i = P; i >= D && a[i - D] > Temp; i -= D){
				a[i] = a[i - D];
			}
			a[i] = Temp;
		}
	}
}
测试点提示内存(KB)用时(ms)结果得分
01762

答案正确

1 / 1
13082

答案正确

10 / 10
23362

答案正确

2 / 2
34124

答案正确

2 / 2
4113230

答案正确

2 / 2
5114421

答案正确

2 / 2
6133222

答案正确

2 / 2
7120422

答案正确

2 / 2
8107627

答案正确

2 / 2

  希尔排序_Hibbard版,就是将增量换成，由2^i 到 2^i-1;达到相邻元素互质，保证有效间隔。

Tworst= O( N^3/2) , Tavg = O ( N^5/4);

void Shell_Sort_Hibbard(int *a, int Num)
{
	int H, D, P, i;
	int Temp;
	int Hibbard[] = {131071, 65535, 32767, 16383, 8191, 4095, 2047, 1023, 511, 255, 127, 63, 31, 15, 7, 3, 1};
	for(H = 0; Hibbard[H] >= Num; H++);
	
	for(D = Hibbard[H]; D > 0; D = Hibbard[++H]){
		for(P = D; P < Num; P++){
			Temp = a[P];
			for(i = P; i >= D && a[i - D] > Temp; i -= D){
				a[i] = a[i - D];
			}
			a[i] = Temp;
		}
	}
}

/*
num1[0] == 0
num1[1] == 1
num1[2] == 3
num1[3] == 7
num1[4] == 15
num1[5] == 31
num1[6] == 63
num1[7] == 127
num1[8] == 255
num1[9] == 511
num1[10] == 1023
num1[11] == 2047
num1[12] == 4095
num1[13] == 8191
num1[14] == 16383
num1[15] == 32767
num1[16] == 65535
num1[17] == 131071
num1[18] == 262143
num1[19] == 524287

*/
测试点提示内存(KB)用时(ms)结果得分
01721

答案正确

1 / 1
13161

答案正确

10 / 10
21802

答案正确

2 / 2
34404

答案正确

2 / 2
4115230

答案正确

2 / 2
5120020

答案正确

2 / 2
6118020

答案正确

2 / 2
7114820

答案正确

2 / 2
8104827

答案正确

2 / 2

   希尔排序_Sedgewick版,这个增量很厉害，9 * 4^i - 9 * 2^i + 1,或 4^i -3 *2^i +1;

Tavg = O ( N^7/6 )，Tworst = O ( N^4/3)

void Shell_Sort_Sedgewick(int *a, int Num)
{
	int Si, D, P, i;
	int Temp;
	int Sedgewick[] = {146305, 64769, 36289, 16001, 8929, 3905, 2161, 929, 505, 209, 109, 41, 19, 5, 1, 0};
	for(Si = 0; Sedgewick[Si] >= Num; Si++);
	
	for(D = Sedgewick[Si]; D > 0; D = Sedgewick[++Si]){
		for(P = D; P < Num; P++){
			Temp = a[P];
			for(i = P; i >= D && a[i - D] > Temp; i -= D){
				a[i] = a[i - D];
			}
			a[i] = Temp;
		}
	}
}

//有同学问，这一序列如何来的，其实是综合两个函数
// 具体的数学逻辑我也不懂
#include <stdio.h>
#include <math.h>

int main()
{
	int i;
	double num1;
	double num2;
	for(i = 0; i < 10; i++){
		num1 = 9.0 * pow(4, i) - 9.0 * pow(2, i) + 1;
		printf("num1[%d] == %.lf\n", i, num1);
	}
	for(i = 0; i < 10; i++){
		num2 = pow(4, i) - 3.0 * pow(2, i) + 1;
		printf("num2[%d] == %.lf\n", i, num2);
	}	
    return 0;
}
/* 这是运行结果：
num1[0] == 1
num1[1] == 19
num1[2] == 109
num1[3] == 505
num1[4] == 2161
num1[5] == 8929
num1[6] == 36289
num1[7] == 146305
num1[8] == 587521
num1[9] == 2354689
num2[0] == -1
num2[1] == -1
num2[2] == 5
num2[3] == 41
num2[4] == 209
num2[5] == 929
num2[6] == 3905
num2[7] == 16001
num2[8] == 64769
num2[9] == 260609
很明显，Sedgewick函数便是如此构成的，
*/
测试点提示内存(KB)用时(ms)结果得分
01722

答案正确

1 / 1
13041

答案正确

10 / 10
23602

答案正确

2 / 2
34324

答案正确

2 / 2
4119628

答案正确

2 / 2
5124020

答案正确

2 / 2
6114820

答案正确

2 / 2
7120020

答案正确

2 / 2
8107225

答案正确

2 / 2

#include<stdio.h>
#include<stdlib.h>

void Bubble_Sort(int *a, int Num); //冒泡排序
void Insert_Sort(int *a, int Num); //插入排序
void Shell_Sort(int *a, int Num); //希尔排序
void Shell_Sort_Hibbard(int *a, int Num); //希尔排序
void Shell_Sort_Sedgewick(int *a, int Num); //希尔排序
//void Selection_Sort(int *a, int Num);// 选择排序
//void Heap_Sort(); //堆排序
//void Merge_Sort(); //归并排序
//void Quick_Sort(); //快速排序
//void Table_Sort(); //表排序
//void Radix_Sort(); //基数排序, 桶排序

int main()
{
	int Num, i;
	int *a;
	scanf("%d", &Num);
	a = (int *)malloc(sizeof(int) * Num);
	for(i = 0; i < Num; i++){
		scanf("%d", &a[i]);
	}
//	Bubble_Sort(a, Num);
//	Insert_Sort(a, Num);
//	Shell_Sort(a, Num);
//	Shell_Sort_Hibbard(a, Num);
//	Shell_Sort_Sedgewick(a, Num);
	Selection_Sort(a, Num);
	for(i = 0; i < Num - 1; i++){
		printf("%d ", a[i]);
	}
	printf("%d\n", a[i]);
	return 0;
}

void Bubble_Sort(int *a, int Num)
{
	int Temp, i, j;
	int flag;
	for(i = 0; i < Num; i++){
		flag = 0;
		for(j = 0; j < Num - 1; j++){
			if(a[j] > a[j + 1]){
				Temp = a[j];
				a[j] = a[j+1];
				a[j+1] = Temp;
				flag = 1;
			}
		}
		if(!flag){
			break;
		}
	}	
}
void Insert_Sort(int *a, int Num)
{
	int i, j;
	int Temp;
	for(i = 1; i < Num; i++){
		Temp = a[i];
		for(j = i; j > 0 && a[j-1] > Temp; j--){
			a[j] = a[j-1];
		}
		a[j] = Temp;
	}
}

void Shell_Sort(int *a, int Num)
{
	int D, P, i;
	int Temp;
	for(D = Num / 2; D > 0; D /= 2){
		for(P = D; P < Num; P++){
			Temp = a[P];
			for(i = P; i >= D && a[i - D] > Temp; i -= D){
				a[i] = a[i - D];
			}
			a[i] = Temp;
		}
	}
}
void Shell_Sort_Hibbard(int *a, int Num)
{
	int H, D, P, i;
	int Temp;
	int Hibbard[] = {131071, 65535, 32767, 16383, 8191, 4095, 2047, 1023, 511, 255, 127, 63, 31, 15, 7, 3, 1};
	for(H = 0; Hibbard[H] >= Num; H++);
	
	for(D = Hibbard[H]; D > 0; D = Hibbard[++H]){
		for(P = D; P < Num; P++){
			Temp = a[P];
			for(i = P; i >= D && a[i - D] > Temp; i -= D){
				a[i] = a[i - D];
			}
			a[i] = Temp;
		}
	}
}

void Shell_Sort_Sedgewick(int *a, int Num)
{
	int Si, D, P, i;
	int Temp;
	int Sedgewick[] = {146305, 64769, 36289, 16001, 8929, 3905, 2161, 929, 505, 209, 109, 41, 19, 5, 1, 0};
	for(Si = 0; Sedgewick[Si] >= Num; Si++);
	
	for(D = Sedgewick[Si]; D > 0; D = Sedgewick[++Si]){
		for(P = D; P < Num; P++){
			Temp = a[P];
			for(i = P; i >= D && a[i - D] > Temp; i -= D){
				a[i] = a[i - D];
			}
			a[i] = Temp;
		}
	}
}
void Selection_Sort(int *a, int Num)
{
	int i,k, Min;
	int Temp, MinValue;
	for(k = 0; k < Num; k++){
		MinValue = 21000000;
		for(i = k; i < Num; i++){
			if(a[i] < MinValue){
				MinValue = a[i];
				Min = i;
			}
		}
		Temp = a[k];
		a[k] = a[Min];
		a[Min] = Temp;
	}
}
选择排序，依旧稳定发挥 
void Selection_Sort(int *a, int Num)
{
	int i,k, Min;
	int Temp, MinValue;
	for(k = 0; k < Num; k++){
		MinValue = 21000000;
		for(i = k; i < Num; i++){
			if(a[i] < MinValue){
				MinValue = a[i];
				Min = i;
			}
		}
		Temp = a[k];
		a[k] = a[Min];
		a[Min] = Temp;
	}
}
测试点提示内存(KB)用时(ms)结果得分
03041

答案正确

1 / 1
13041

答案正确

10 / 10
23082

答案正确

2 / 2
332055

答案正确

2 / 2
46323000

运行超时

0 / 2
56083000

运行超时

0 / 2
65603000

运行超时

0 / 2
76963000

运行超时

0 / 2
85523000

运行超时

0 / 2

 堆排序_简单版

测试点提示内存(KB)用时(ms)结果得分
0只有一个元素1803000

运行超时

0 / 1
11721

答案正确

10 / 10
23562

答案正确

2 / 2
34324

答案正确

2 / 2
4118027

答案正确

2 / 2
5126423

答案正确

2 / 2
6120423

答案正确

2 / 2
7122022

答案正确

2 / 2
8102026

答案正确

2 / 2
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>


typedef struct Heap *MinHeap;
struct Heap{
	int *data;
	int Size;
};
void Selection_Sort(int *a, int Num);// 选择排序
void Heap_Sort_Easy(int *a, int Num); //堆排序
void Swap(int *a, int *b);
MinHeap Creat_Heap(int *a, int N);
MinHeap Init_Heap(int N);
void Insert_Heap(MinHeap H, int data);
int Delete_Heap(MinHeap H);
bool IsEmpty(MinHeap H);

int main()
{
	int Num, i;
	int *a;
	scanf("%d", &Num);
	a = (int *)malloc(sizeof(int) * Num);
	for(i = 0; i < Num; i++){
		scanf("%d", &a[i]);
	}
//	Selection_Sort(a, Num);
	Heap_Sort_Easy(a, Num);
	for(i = 0; i < Num - 1; i++){
		printf("%d ", a[i]);
	}
	printf("%d\n", a[i]);
	free(a);
	return 0;
}

void Selection_Sort(int *a, int Num)
{
	int i,k, Min;
	int Temp, MinValue;
	for(k = 0; k < Num; k++){
		MinValue = 21000000;
		for(i = k; i < Num; i++){
			if(a[i] < MinValue){
				MinValue = a[i];
				Min = i;
			}
		}
		Swap(&a[k], &a[Min]);
	}
}
void Heap_Sort_Easy(int *a, int Num)
{
	MinHeap H;
//	if(Num == 1){
//		return ;
//	}
	H = Creat_Heap(a, Num);
	for(int i = 0; i < Num; i++){
		a[i] = Delete_Heap(H);
	}
	free(H ->data);
	free(H);
}
void Swap(int *a, int *b)
{
	int Temp;
	Temp = *a;
	*a = *b;
	*b = Temp;
}
MinHeap Creat_Heap(int *a, int N)
{
	MinHeap H;
	H = Init_Heap(N);
	for(int i = 0; i < N; i++){
		Insert_Heap(H, a[i]);
	}
	return H;
}
MinHeap Init_Heap(int N)
{
	MinHeap H;
	H = (MinHeap)malloc(sizeof(struct Heap));
	H ->data = (int*)malloc(sizeof(int) * (N + 1));
	H ->data[0] = -2100000;
	H ->Size = 0;
	return H;
}
void Insert_Heap(MinHeap H, int data)
{
	int i;
	i = ++H ->Size;
	for(; data < H ->data[i/2]; i /=2){
		H ->data[i] = H ->data[i/2];
	}
	H ->data[i] = data;
}
int Delete_Heap(MinHeap H)
{
	int Parent, Child, i;
	int Min, Temp;
	if(IsEmpty(H)){
		printf("Is error!\n");
		return H ->data[0];
	}
	Min = H ->data[1];
	Temp = H ->data[H ->Size --];
	for(Parent = 1; Parent * 2 <= H ->Size; Parent = Child){
		Child = Parent * 2;
		if(H ->data[Child] > H ->data[Child + 1]){
			Child++;
		}
		if(Temp <= H ->data[Child]){
			break;
		}else{
			H ->data[Parent] = H ->data[Child];
		}
	}
	H ->data[Parent] = Temp;
	return Min;
}
bool IsEmpty(MinHeap H)
{
	return (H ->Size == 0);
}

  堆排序_进阶版

测试点提示内存(KB)用时(ms)结果得分
01682

答案正确

1 / 1
13041

答案正确

10 / 10
23682

答案正确

2 / 2
34324

答案正确

2 / 2
4118828

答案正确

2 / 2
5127223

答案正确

2 / 2
6127623

答案正确

2 / 2
7115222

答案正确

2 / 2
894426

答案正确

2 / 2
#include<stdio.h>
#include<stdlib.h>

void Heap_Sort_Good(int *a, int Num); //堆排序
void Swap(int *a, int *b);
void PercDown(int *a, int index, int Num);

int main()
{
	int Num, i;
	int *a;
	scanf("%d", &Num);
	a = (int *)malloc(sizeof(int) * Num);
	for(i = 0; i < Num; i++){
		scanf("%d", &a[i]);
	}
	Heap_Sort_Good(a, Num);
	for(i = 0; i < Num - 1; i++){
		printf("%d ", a[i]);
	}
	printf("%d\n", a[i]);
	return 0;
}

void Heap_Sort_Good(int *a, int Num)
{
	int i, j;
	for(i = Num / 2 - 1; i >= 0;i--){
		PercDown(a, i, Num);
	}
	for(i = Num - 1; i > 0; i--){
		Swap(&a[0], &a[i]);
		PercDown(a, 0, i);
	}
}
void PercDown(int *a, int index, int Num)
{
	int Parent, Child;
	int Value;
	Value = a[index];
	for(Parent = index; (Parent * 2 + 1) < Num; Parent = Child){
		Child  = Parent * 2 + 1;
		if((Child != Num - 1) && a[Child] < a[Child + 1]){
			Child++;
		}
		if(Value >= a[Child]){
			break;
		}else{
			a[Parent] = a[Child];
		}
	}
	a[Parent] = Value;
}

void Swap(int *a, int *b)
{
	int Temp;
	Temp = *a;
	*a = *b;
	*b = Temp;
}

 归并排序递归版

测试点提示内存(KB)用时(ms)结果得分
03642

答案正确

1 / 1
13362

答案正确

10 / 10
23682

答案正确

2 / 2
34645

答案正确

2 / 2
4117628

答案正确

2 / 2
5129221

答案正确

2 / 2
6118424

答案正确

2 / 2
7126421

答案正确

2 / 2
8106425

答案正确

2 / 2
#include<stdio.h>
#include<stdlib.h>

//归并排序
void Merge_Sort(int *a, int Num);
void Msort(int *a, int *t, int LeftStart, int RightEnd);
void Merge(int *a, int *t, int LeftStart, int RightStart, int RightEnd);

int main()
{
	int Num, i;
	int *a;
	scanf("%d", &Num);
	a = (int *)malloc(sizeof(int) * Num);
	for(i = 0; i < Num; i++){
		scanf("%d", &a[i]);
	}
	Merge_Sort(a, Num);
	for(i = 0; i < Num - 1; i++){
		printf("%d ", a[i]);
	}
	printf("%d\n", a[i]);
	return 0;
}

void Merge_Sort(int *a, int Num)
{
	int *t;
	t = (int *)malloc(sizeof(int) * Num);
	if(t != NULL){
		Msort(a, t, 0, Num - 1);
		free(t);
	}
}
void Msort(int *a, int *t, int LeftStart, int RightEnd)
{
	int center;
	if(LeftStart < RightEnd){
		center = ((LeftStart + RightEnd) / 2);
		Msort(a, t, LeftStart, center);
		Msort(a, t, center + 1, RightEnd);
		Merge(a, t, LeftStart, center + 1, RightEnd);
		
	}
}
void Merge(int *a, int *t, int LeftStart, int RightStart, int RightEnd)
{
	int LeftEnd, Nums;
	int Temp;
	LeftEnd = RightStart - 1;
	Temp = LeftStart;
	Nums = RightEnd - LeftStart + 1;
	while((LeftStart <= LeftEnd) && (RightStart <= RightEnd)){
		if(a[LeftStart] <= a[RightStart]){
			t[Temp++] = a[LeftStart++];
		}else{
			t[Temp++] = a[RightStart++];
		}
	}
	while(LeftStart <= LeftEnd){
		t[Temp++] = a[LeftStart++];
	}
	while(RightStart <= RightEnd){
		t[Temp++] = a[RightStart++];
	}
	for(int i = 0; i < Nums; i++, RightEnd--){
		a[RightEnd] = t[RightEnd];
	}
}

  归并排序-非递归版

测试点提示内存(KB)用时(ms)结果得分
01762

答案正确

1 / 1
11802

答案正确

10 / 10
23562

答案正确

2 / 2
34325

答案正确

2 / 2
4130026

答案正确

2 / 2
5129620

答案正确

2 / 2
6114820

答案正确

2 / 2
7113619

答案正确

2 / 2
8106424

答案正确

2 / 2
#include<stdio.h>
#include<stdlib.h>

//归并排序
void Merge_Sort(int *a, int Num);
void Msort(int *a, int *t, int Num, int Length);
void Merge(int *a, int *t, int LeftStart, int RightStart, int RightEnd);

int main()
{
	int Num, i;
	int *a;
	scanf("%d", &Num);
	a = (int *)malloc(sizeof(int) * Num);
	for(i = 0; i < Num; i++){
		scanf("%d", &a[i]);
	}
	Merge_Sort(a, Num);
	for(i = 0; i < Num - 1; i++){
		printf("%d ", a[i]);
	}
	printf("%d\n", a[i]);
	return 0;
}

void Merge_Sort(int *a, int Num)
{
	int *t;
	int Length = 1;
	t = (int *)malloc(sizeof(int) * Num);
	if(t != NULL){
		while(Length < Num){
			Msort(a, t, Num, Length);
			Length *= 2;
			Msort(t, a, Num, Length);
			Length *= 2;
		}
		free(t);
	}
}
void Msort(int *a, int *t, int Num, int Length)
{
	int i, j;
	for(i = 0; i <= (Num - 2 * Length); i += 2 * Length){
		Merge(a, t, i, i + Length, (i + 2 * Length) - 1);
	}
	if(i + Length < Num){
		Merge(a, t, i, i + Length, Num - 1);
	}else{
		for(j = i; j < Num; j++){
			t[j] = a[j];
		}
	}
}
void Merge(int *a, int *t, int LeftStart, int RightStart, int RightEnd)
{
	int LeftEnd, Nums;
	int Temp;
	LeftEnd = RightStart - 1;
	Temp = LeftStart;
	Nums = RightEnd - LeftStart + 1;
	while((LeftStart <= LeftEnd) && (RightStart <= RightEnd)){
		if(a[LeftStart] <= a[RightStart]){
			t[Temp++] = a[LeftStart++];
		}else{
			t[Temp++] = a[RightStart++];
		}
	}
	while(LeftStart <= LeftEnd){
		t[Temp++] = a[LeftStart++];
	}
	while(RightStart <= RightEnd){
		t[Temp++] = a[RightStart++];
	}
}

 快速排序_自定义版

测试点提示内存(KB)用时(ms)结果得分
03602

答案正确

1 / 1
13562

答案正确

10 / 10
22722

答案正确

2 / 2
33445

答案正确

2 / 2
4114431

答案正确

2 / 2
5120818

答案正确

2 / 2
6129219

答案正确

2 / 2
7120419

答案正确

2 / 2
894428

答案正确

2 / 2
#include<stdio.h>
#include<stdlib.h>

//归并排序

void Swap(int *a, int *b);
int Median3(int *a, int Left, int Right);
void Qsort(int *a, int Left, int Right);
void Quick_Sort(int *a, int Num);
void Insert_Sort(int *a, int Num);

int main()
{
	int Num, i;
	int *a;
	scanf("%d", &Num);
	a = (int *)malloc(sizeof(int) * Num);
	for(i = 0; i < Num; i++){
		scanf("%d", &a[i]);
	}
	Quick_Sort(a, Num);
	for(i = 0; i < Num - 1; i++){
		printf("%d ", a[i]);
	}
	printf("%d\n", a[i]);
	return 0;
}
int Median3(int *a, int Left, int Right)
{
	int Center = (Left + Right)/2;
	if(a[Left] > a[Center]){
		Swap(&a[Left], &a[Center]);
	}
	if(a[Left] > a[Right]){
		Swap(&a[Left], &a[Right]);
	}
	if(a[Center] > a[Right]){
		Swap(&a[Center], &a[Right]);
	}
	Swap(&a[Center], &a[Right - 1]);
	return a[Right - 1];
}
void Qsort(int *a, int Left, int Right)
{
	int Pivot, Cutoff, i, j; 
	Cutoff = 1000;
	if(Cutoff < Right - Left){
		Pivot = Median3(a, Left, Right);
		i = Left; j = Right-1;
		while(1){
			while(a[++i] < Pivot);
			while(a[--j] > Pivot);
			if(i < j){
				Swap(&a[i], &a[j]);
			}else{
				break;
			}
		}
		Swap(&a[i], &a[Right - 1]);
		Qsort(a, Left, i - 1);
		Qsort(a, i + 1, Right);
	}
	else{
		Insert_Sort(a + Left, Right - Left + 1);
	}
}
void Quick_Sort(int *a, int Num)
{
	Qsort(a, 0, Num - 1);
}
void Swap(int *a, int *b)
{
	int Temp;
	Temp = *a;
	*a = *b;
	*b = Temp;
}
void Insert_Sort(int *a, int Num)
{
	int i, j;
	int Temp;
	for(i = 1; i < Num; i++){
		Temp = a[i];
		for(j = i; j > 0 && a[j-1] > Temp; j--){
			a[j] = a[j-1];
		}
		a[j] = Temp;
	}
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.mfbz.cn/a/875203.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

【代码随想录训练营第42期 Day57打卡 - 图论Part7 - Prim算法

【代码随想录训练营第42期 Day57打卡 - 图论Part7 - Prim算法

一、Prim算法 Prim算法是一种贪心算法&#xff0c;用于求解加权无向图的最小生成树问题。其中&#xff0c;最小生成树是指一个边的子集&#xff0c;它连接图中的所有顶点&#xff0c;且边的总权重最小&#xff0c;并且没有形成环。 对于Prim算法的简单了解&#xff0c;这里推…
阅读更多...
基于小程序的教学辅助微信小程序设计+ssm（lw+演示+源码+运行）

基于小程序的教学辅助微信小程序设计+ssm（lw+演示+源码+运行）

教学辅助微信小程序 摘 要 随着移动应用技术的发展&#xff0c;越来越多的学生借助于移动手机、电脑完成生活中的事务&#xff0c;许多的传统行业也更加重视与互联网的结合&#xff0c;由于学生学习的压力越来越大&#xff0c;教学辅助是一个非常不错的教育平台&#xff0c;对…
阅读更多...
9.12-kubeadm方式安装k8s+基础命令的使用

9.12-kubeadm方式安装k8s+基础命令的使用

一、安装环境 编号主机名称ip地址1k8s-master192.168.2.662k8s-node01192.168.2.773k8s-node02192.168.2.88 二、前期准备 1.设置免密登录 [rootk8s-master ~]# ssh-keygen[rootk8s-master ~]# ssh-copy-id root192.168.2.77[rootk8s-master ~]# ssh-copy-id root192.168.2.…
阅读更多...
指令——计算机的语言(part 2)

指令——计算机的语言(part 2)

目录 1.1 翻译并执行程序 1.1.1 编译器 1.1.2 汇编器 1.1.3 链接器 1.1.4 加载器 1.1.5 动态链接库 接上一篇文章: 指令——计算机的语言(part 1) 1.1 翻译并执行程序 程序翻译层次图如下: 首先高级语言比如说C&#xff0c;会被编译器编译成汇编语言&#xff0c;然后汇…
阅读更多...
Python面试宝典第48题：找丑数

Python面试宝典第48题：找丑数

题目 我们把只包含质因子2、3和5的数称作丑数&#xff08;Ugly Number&#xff09;。比如&#xff1a;6、8都是丑数&#xff0c;但14不是&#xff0c;因为它包含质因子7。习惯上&#xff0c;我们把1当做是第一个丑数。求按从小到大的顺序的第n个丑数。 示例 1&#xff1a; 输入…
阅读更多...
另类动态规划

另类动态规划

前言&#xff1a;一开始我根本想不到这个题目是一个动态规划的题目&#xff0c;而且我一开始的初始状态还写错了 我还忘记了写算法题的基本步骤&#xff0c;先看数据范围&#xff0c;再考虑能不能用动态规划写 题目地址 #include <bits/stdc.h> using namespace std; #de…
阅读更多...
3C电子胶黏剂在手机制造方面有哪些关键的应用

3C电子胶黏剂在手机制造方面有哪些关键的应用

3C电子胶黏剂在手机制造方面有哪些关键的应用 3C电子胶黏剂在手机制造中扮演着至关重要的角色&#xff0c;其应用广泛且细致&#xff0c;覆盖了手机内部组件的多个层面&#xff0c;确保了设备的可靠性和性能。以下是电子胶在手机制造中的关键应用&#xff1a; 手机主板用胶&…
阅读更多...
浏览器百科：网页存储篇-IndexedDB介绍（十）

浏览器百科：网页存储篇-IndexedDB介绍（十）

1.引言 在现代网页开发中&#xff0c;数据存储需求日益增多和复杂&#xff0c;传统的客户端存储技术如localStorage和sessionStorage已难以满足大型数据的存储和管理需求。为了解决这一问题&#xff0c;HTML5 引入了 IndexedDB&#xff0c;在本篇《浏览器百科&#xff1a;网页…
阅读更多...
网络学习-eNSP配置路由器

网络学习-eNSP配置路由器

#PC1网关&#xff1a;192.168.1.254 #PC3网关&#xff1a;192.168.3.254 #PC4网关&#xff1a;192.168.4.254# 注&#xff1a;路由器接口必须配置不同网段IP地址 <Huawei>system-view Enter system view, return user view with CtrlZ. #给路由器两个接口配置IP地址 [Hua…
阅读更多...
IBM中国研发中心撤出：挑战与机遇并存

IBM中国研发中心撤出：挑战与机遇并存

IBM中国研发中心撤出&#xff1a;挑战与机遇并存 引言 近日&#xff0c;IBM宣布撤出在中国的两大研发中心的消息&#xff0c;引起了广泛关注。这一举动不仅对IBM自身的全球布局产生了影响&#xff0c;也在一定程度上反映了跨国公司在中国市场策略的调整。本文将探讨这一事件背…
阅读更多...
keras和tensorflow可用的一组版本

keras和tensorflow可用的一组版本

目录 keras版本&#xff1a;3.5.0tensorflow&#xff1a;2.17.0之前的错误导包现在的正确导包 keras版本&#xff1a;3.5.0 tensorflow&#xff1a;2.17.0 之前的错误导包 其实也不是说错误&#xff0c;就是因为文件位置不对&#xff0c;所以VSCode总是有黄色波浪线&#xff0…
阅读更多...
只出现一次的数II

只出现一次的数II

只出现一次的数&#xff1a;力扣&#xff08;LeetCode&#xff09;-----只出现一次的数 题目描述 给你一个整数数组 nums &#xff0c;除某个元素仅出现 一次 外&#xff0c;其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。 示例 1&#xff1a; 输入&am…
阅读更多...
C# WinForm：禁用Panel容器滚动条自动移动位置的功能

C# WinForm：禁用Panel容器滚动条自动移动位置的功能

1.在WinForm项目中新建一个类&#xff1a; 2.类里面的内容&#xff0c;重写Panel的这个方法 3.编译后这个控件就出现在工具箱了 4.然后用这个新Panel控件就好了 5.完事大吉。
阅读更多...
Datasheet SHT20芯片的数据手册

Datasheet SHT20芯片的数据手册

Datasheet SHT20芯片的数据手册 I2C读取湿度传感器返回的16位数据。SCL SDA 14位有效&#xff0c;我以为是将后二位删除&#xff0c;实际上看完手册才知道是后二位值无用&#xff0c;不是删除&#xff0c;而是清0&#xff0c;实际上还是16为&#xff0c;知识后二位是0还是1&…
阅读更多...
深度学习——基础知识

深度学习——基础知识

深度学习的重点在于优化&#xff0c;其中很重要的步骤在于如何调参&#xff0c;会涉及到一些微积分等数学知识。不同于以往接触到的数值运算&#xff0c;深度&#xff08;机器&#xff09;学习都是关于张量Tensor&#xff08;向量&#xff09;的计算&#xff0c;Python中最常用…
阅读更多...
leetcode21. 合并两个有序链表

leetcode21. 合并两个有序链表

思路&#xff1a; 用一个新链表来表示合并后的有序链表&#xff0c; 每次比较两个链表&#xff0c;将较小的那个结点存储至新链表中 # Definition for singly-linked list. # class ListNode(object): # def __init__(self, val0, nextNone): # self.val val # …
阅读更多...
机器学习（西瓜书）第 9 章 聚类

机器学习（西瓜书）第 9 章 聚类

9.1 聚类任务和距离计算 在”无监督学习“中&#xff0c;训练样本的标记信息是未知的&#xff0c;目标是通过对无标记训练样本的学习来揭示数据的内在性质及规律&#xff0c;为进一步的数据分析提供基础.此类学习任务中研究最多、应用最广的是“聚类”(clustering). 聚类试图…
阅读更多...
动手学深度学习（pytorch）学习记录30-含并行连接的网络(GoogLeNet)[学习记录]

动手学深度学习（pytorch）学习记录30-含并行连接的网络(GoogLeNet)[学习记录]

目录 GoogLeNetInception块GoogLeNet模型训练模型 GoogLeNet GoogLeNet&#xff0c;也称为Inception v1&#xff0c;是由Google团队在2014年提出的深度学习模型&#xff0c;它在当年的ImageNet竞赛中取得了显著的成绩。GoogLeNet的设计引入了多个创新点&#xff0c;包括Incept…
阅读更多...
【C++】string类的基本使用

【C++】string类的基本使用

一、string类的由来 在C语言中&#xff0c;字符串是以\0结尾的一些字符的集合&#xff0c;为了操作方便&#xff0c;C标准库中提供了一些str系列 的库函数&#xff0c;但是这些库函数与字符串是分离开的&#xff0c;不太符合OOP的思想&#xff0c;而且底层空间需要用户 自己管…
阅读更多...
大数据之Flink（三）

大数据之Flink（三）

9.3、转换算子 9.3.1、基本转换算子 9.3.1.1、映射map 一一映射 package transform;import bean.WaterSensor; import org.apache.flink.streaming.api.datastream.DataStreamSource; import org.apache.flink.streaming.api.datastream.SingleOutputStreamOperator; impor…
阅读更多...
最新文章

Copyright @ 2022~2023