yuzh的博客

❤ ECUST ❤

0%

排序算法综合

发表于 Valine：

下方所有除使用STL库外的所有排序算法调用方法都是qsort(a,0,n-1);

初级排序算法

冒泡排序

1
2
3
4
5
6
7
8
9
10
void bubblesort(int* arr, int left, int right)
{
	for(int i=left;i<=right;i++)
	{
		for(int j=i+1;j<=right;j++)
		{
			if(arr[i]>arr[j]) swap(arr[i],arr[j]);
		}
	}
}

选择排序

1
2
3
4
5
6
7
8
9
10
11
12
void selectionsort(int* arr, int left, int right)
{
	for(int i=left;i<=right;i++)
	{
		int min=i; 
		for(int j=i+1;j<=right;j++)
		{
			if(arr[j]<arr[min]) min=j;
		}
		swap(arr[i],arr[min]);
	}
}

插入排序

同整理扑克牌，依次将每个元素插入到前面有序的部分。

1
2
3
4
5
6
7
8
9
10
11
void insertionsort(int* arr, int left, int right)
{
	for(int i=left;i<=right;i++)
	{
		int cnt=arr[i];
		for(int j=i-1;j>=left && cnt<=arr[j];j--)
		{
			swap(arr[j],arr[j+1]);
		}
	}
}

优化：可以利用折半查找的方法找到插入的位置，即折半插入排序

希尔排序

通过给定间隔h，使得原来的数组被切分为更小的数组，进而提升插入排序效率

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void shellsort(int* arr, int left, int right)
{
	int h=1;
	while(h<(right-left+1)/3) h=h*3+1;
	while(h>=1)
	{
		for(int i=left;i<(right-left+1)/h;i++)
		{
			int cnt=arr[i];
			for(int j=i-h;j>=left && cnt<=arr[j];j-=h)
			{
				swap(arr[j],arr[j+h]);
			}
		}
		h/=3; 
	}
}

进阶排序算法

归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void merge(int* arr, int left, int mid, int right)
{
	int aux[10000], i=left, j=mid+1;
	for(int k=left;k<=right;k++) aux[k]=arr[k];
	for(int k=left;k<=right;k++)
	{
		if(i>mid) arr[k]=aux[j++];
		else if(j>right) arr[k]=aux[i++];
		else if(aux[j]<aux[i]) arr[k]=aux[j++];
		else arr[k]=aux[i++];
	}
}

void mergesort(int* arr, int left, int right)
{
	if(left<right)
	{
		int mid=(right+left)/2;
		mergesort(arr,left,mid);
		mergesort(arr,mid+1,right);
		merge(arr,left,mid,right);
	}
}

快速排序

  • partition函数：以当前给定集合的第一个元素pivot作为基准，比其小的放在左边，比其大的放在右边
  • 随后对pivot左右的数组分别进行排序，直至left=right结束分治

手写快排

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int partition(int* arr, int left, int 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; //arr[right]=pivot;
	return left;
}

void qsort(int* arr, int left, int right)
{
	if(left<right)
	{
		int pivot=partition(arr,left,right);
		qsort(arr,left,pivot-1);
		qsort(arr,pivot+1,right);
	}
}

STL sort

排序规则

1
2
3
4
5
//调用：sort(a,a+n,cmp);
bool cmp(int a, int b)
{
	return a<b;
}