十大排序算法总结
查找和排序算法是算法的入门知识，也经常在面试中出现，要求现场写代码，因此熟悉常用的排序思想和代码很重要。主要的排序方法有冒泡排序、直接插入排序、选择排序、快速排序、归并排序、堆排序、希尔排序、计数排序、桶排序、基数排序。
直接插入排序
- 算法思想
整个排序过程是n-1趟插入，即先将序列中第一个数字看成是有序数据，然后从第2个数据开始，逐个进行插入，直至整个序列有序。如下图：
实现代码
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
27
28
29
30
31
32
33
34
35
36
37
38
using namespace std;
void helpCout(int* nums, int n)
{
for(int i=0; i<n; i++)
{
cout<<nums[i]<<" ";
}
cout<<endl;
}
// ********** 直接插入排序 **********
// 数组
void insertSort(int* nums, int n)
{
for(int i=0; i<n; i++)
{
int j = i;
int insert = nums[i];
while(j>0 and nums[j-1] > insert)
{
nums[j] = nums[j-1];
j--;
}
nums[j] = insert;
}
}
int main()
{
int nums[] = {2,5,1,7,3,9,5,0};
cout<<"nums: ";
int n = sizeof(nums)/ sizeof(nums[0]);
helpCout(nums, n);
insertSort(nums, n);
cout<<"sort result: "<<endl;
helpCout(nums, n);
}
运行结果
1
2
3nums: 2 5 1 7 3 9 5 0
sort result:
0 1 2 3 5 5 7 9
希尔排序
- 算法思想
希尔排序的基本思想是对待排序列先做“宏观”调整，再作“微观”调整。“宏观”指的是跳跃式的插入排序。 实现代码
1
交换排序
交换排序的基本思想是两两比较待排序对象的数值，如果发生逆序，则交换，直到所有排序对象都排好序为止。交换排序主要有冒泡排序和快速排序。
冒泡排序
算法思想
第一趟：第1个数与第2个数比较，大则交换；第2个数与第3个数比较，大则交换；…;第n-1个数与第n个数比较，大则交换；第n个位置得到最大的数；
第二趟：对前n-1个数进行同样的操作，第n-1个位置得到次大的数，此时第n-1个数和第n个数已经排好序；
以此类推，n-1趟完成排序。
实现代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18// ************* 冒泡排序 **************
void bubble(int* nums, int n)
{
for(int i=1; i<n; i++)
{
int j = 0;
while(j<n-i)
{
if(nums[j] > nums[j+1])
{
int tmp = nums[j+1];
nums[j+1] = nums[j];
nums[j] = tmp;
}
j++;
}
}
}
快速排序
算法思想
实现代码
1
选择排序
算法思想
实现代码
1
归并排序
算法思想
实现代码
1
堆排序
算法思想
实现代码
1
计数排序
算法思想
实现代码
1
桶排序
算法思想
实现代码
1
基数排序
算法思想
实现代码
1