菜鸟笔记
提升您的技术认知

八大排序算法及其优化

阅读 : 145

常见的排序算法

1. 直接插入排序

(1)算法基本思想

(2)特性总结:

  1. 元素集合越接近有序,直接插入算法的时间效率越高
  2. 时间复杂度:O(N^2)
  3. 空间复杂度:O(1),它是一种稳定的排序算法
  4. 稳定性:稳定

(3)代码实现:

void InsertSort(int* a, int n)
{ 
	for (int i = 0; i < n - 1; i++)
	{ 
		int end = i;
		int tmp = a[end + 1];
		while ()
		{ 
			if (tmp > a[end])
			{ 
				a[end + 1] = a[end];
				end--;

				a[end + 1] = tmp;
			}
			else
				break;
		}
	}
}

2. 希尔排序

(1)算法基本思想

(2)特性总结:

  1. 希尔排序是对直接插入排序的优化
  2. 当gap > 1时都是预排序,目的是让数组更接近于有序。当gap == 1时,数组已经接近有序了,这样就会很快。这样整体而言,可以达到优化的效果。
  3. 希尔排序的时间复杂度不好计算,需要进行推导,推导出来平均时间复杂度: O(N1.3—N2)
  4. 稳定性:不稳定

(3)代码实现:

void ShellSort(int* a, int n)
{ 
	int gap = n;
	while (gap > 1)
	{ 
		gap = gap / 3 + 1;
		for (int i = 0; i < n - gap; i++)
		{ 
			if (a[i] > a[i + gap])
			{ 
				int tmp = a[i];
				a[i] = a[i + gap];
				a[i + gap] = tmp;
			}
		}
	}
}

3. 直接选择排序

(1)算法基本思想

(2)特性总结:

  1. 直接选择排序思考非常好理解,但是效率不是很好。实际中很少使用
  2. 时间复杂度:O(N^2)
  3. 空间复杂度:O(1)
  4. 稳定性:不稳定

(3)代码实现

void SelectSort(int* a, int n)
{ 
	int min = 0;
	int max = 0;
	
		for (int i = 0; i<n-1; i++)
		{ 
			min = i;
			
				for (int j = i; j < n-1; j++)
				{ 
					if (a[min] > a[j + 1])
					{ 
						min = j + 1;
					}
					
				}
				Swap(&a[min], &a[i]);
		}		
}

4. 堆排序

需要注意的是排升序要建大堆,排降序建小堆。

(1)算法基本思想

堆排序的基本思想是:将待排序序列构造成一个大顶堆,此时,整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换,此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆,这样会得到n个元素的次小值。如此反复执行,便能得到一个有序序列了
(2)特性总结

  1. 堆排序使用堆来选数,效率就高了很多
  2. 时间复杂度:O(N*logN)
  3. 空间复杂度:O(1)
  4. 稳定性:不稳定

(3)代码实现

void AjustDown(int* a, int root, int n)
{ 
	int parent = root;
	int child = parent * 2 + 1;
	while (child < n)
	{ 
		if (a[child] < a[child + 1] && child + 1 < n)
			++child;
		if (a[child] > a[parent])
		{ 
			int tmp = parent;
			parent = a[child];
			a[child] = tmp;

			parent = child;
			child = parent * 2 + 1;
		}
		else
			break;
	}
}
void HeapSort(int* a, int root, int n)
{ 
	//建大堆
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{ 
		AjustDown(a, i, n);
	}

	int end = n;
	for (int i = end; i >= 0; i--)
	{ 
		swap(a[0], a[end]);
		AjustDown(a, 0, i);
	}
}

5. 冒泡排序

(1)基本思想

(2)特性总结

  1. 冒泡排序是一种非常容易理解的排序
  2. 时间复杂度:O(N^2)
  3. 空间复杂度:O(1)
  4. 稳定性:稳定

(3)代码实现

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

6. 快排

(1)基本思想

(2)特性总结

  1. 快排整体的综合性能和使用场景都是比较好的,所以才敢叫快速排序
  2. 时间复杂度:O(N*logN)
  3. 空间复杂度:O(logN)
  4. 稳定性:不稳定

(3)代码实现
代码1:

#include<stdio.h>
#include<stdlib.h>
int a[100], n;
void quicksort(int left, int right)
{ 
	int i;//指向第一个数
	int j;//指向最后一个数
	int tmp;//存基准数
	if (left > right)
		return;
	tmp = a[left];
	i = left;
	j = right;
	while (i != j)
	{ 
		while (i < j && a[j] >= tmp)
		{ 
			j--;
		}
		while (i < j && a[i] <= tmp)
		{ 
			i++;
		}
		if (i < j)
		{ 
			int t = a[i];
			a[i] = a[j];
			a[j] = t;
		}
	}
	//最终将基准数归位
	a[left] = a[i];
	a[i] = tmp;
	quicksort(left, i - 1);//继续处理左边的,这里是一个递归的过程
	quicksort(i + 1, right);//继续处理右边的 ,这里是一个递归的过程
}
int main()
{ 
	int i;
	//读入数据
	scanf("%d", &n);
	for (i = 1; i <= n; i++)
		scanf("%d", &a[i]);
	quicksort(1, n); //快速排序调用
	//输出排序后的结果
	for (i = 1; i < n; i++)
		printf("%d ", a[i]);

	system("pause");
	return 0;
}

代码2:

//这里还有一种简单的,通俗易懂的快速排序方法,代码如下:

#include <stdio.h>

void swap(int a[],int i,int j)
{ 
	int t;
	t=a[i];
	a[i]=a[j];
	a[j]=t;
}

void quickSort(int a[],int left,int right)
{ 
	int mid,i,j;

	if(left>=right)
		return;

	mid = a[left];
	i=left;
	j=left+1;
	while(j<=right)
	{ 
		if(a[j]<=mid)
		{ 
			i++;
			swap(a,i,j);
		}
		j++;
	}
	swap(a,i,left);
	quickSort(a,left,i-1);
	quickSort(a,i+1,right);
}

int main()
{ 
	int a[9]={ 8,2,6,12,1,9,5,5,10};
	int i;
	quickSort(a,0,8);/*排好序的结果*/
	for(i=0;i<9;i++)
	printf("%d\n",a[i]);
	return 0;
}

观察上面代码可知,j一直在向后移,而i只有在发生交换操作后才后移。可见,小于等于i坐标的数值都是小于等于mid值的,大于i坐标的数值都是大于mid值的。

i是先加1再交换的。

简单吧,通俗易懂吧,哈哈,希望对大家有帮助!

7. 归并排序

(1)基本思想

(2)特性总结

  1. 归并排序的缺点在与需要O(N)的空间复杂度,归并排序的思考更多的是解决在磁盘中的外排问题
  2. 时间复杂度:O(N*logN)
  3. 空间复杂度:O(N)
  4. 稳定性:稳定

(3)代码实现

void _MergeSort(int* a, int left, int right, int* tmp)
{ 
	if (left >= left)
		return;
	//将它分为两部分
	int mid = left + ((right - left) >> 1);
	//[left, mid]
	//[mid+1, right]
	_MergeSort(a, left, mid, tmp);
	_MergeSort(a, mid + 1, right, tmp);

	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;
	int index = left;

	while (begin1 <= end1 && begin2 <= end2)
	{ 
		if (a[begin1] < a[begin2])
			tmp[index++] = a[begin1++];
		else
			tmp[index++] = a[begin2++];
	}
	while (begin1 <= end1)
		tmp[index++] = a[begin1++];
	while (begin2 <= end2)
		tmp[index++] = a[begin2++];

	memcpy(a + left, tmp + left, sizeof(int)*(right - left + 1));
}