排序分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。
我们这里的八大排序就是内部排序。
快速排序:是目前基于比较的内部排序中被认为是最好的方法,当待排序的关键字是随机分布时,快速排序的平均时间最短;
冒泡排序
基本思想:
在要排序的一组数中,对当前还未排好序的范围内的全部数,自上而下对相邻的两个数依次进行比较和调整,让较大的数往下沉,较小的往上冒。即:每当两相邻的数比较后发现它们的排序与排序要求相反时,就将它们互换。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21//冒泡排序
void BubbleSort(int *array,int size)
{
int flag = 1;
for (int i = 0; i < size; i++)
{
flag = 0;
for (int j = i+1; j < size; j++)
{
if (array[i]>array[j])
{
Swap(&array[i],&array[j]);
}
}
if (flag == 1)
{
break;
}
}
}
选择排序
单向选择排序
基本思想:
在要排序的一组数中,选出最小(或者最大)的一个数与第1个位置的数交换;然后在剩下的数当中再找最小(或者最大)的与第2个位置的数交换,依次类推,直到第n-1个元素(倒数第二个数)和第n个元素(最后一个数)比较为止。
操作方法:
第一趟,从n 个记录中找出关键码最小的记录与第一个记录交换;
第二趟,从第二个记录开始的n-1 个记录中再选出关键码最小的记录与第二个记录交换;
以此类推…..
第i 趟,则从第i 个记录开始的n-i+1 个记录中选出关键码最小的记录与第i 个记录交换,
直到整个序列按关键码有序。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20//选择排序
void SelectSort(int *array,int size)
{
int min;
for (int i = 0; i < size; i++)
{
min = i;
for (int j = i; j < size; j++)
{
if (array[j] < array[min])
{
min = j;
}
}
if (i != min)
{
Swap(&array[min],&array[i]);
}
}
}
双向选择排序
基本思路
与单向选择排序一样,在从头部开始排序的同时,我们让其从末端也进行排序,当前后前后两个下标索引相遇就停止,具体代码如下: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//双向选择排序
void SelectSort(int arr[],int size)
{
int minSpace = 0;
int maxSpace = size - 1;
while (minSpace < maxSpace)
{
int minPos = minSpace;
int maxPos = minSpace;
for (int i = minSpace +1; i <= maxSpace; i++)
{
if (arr[i] > arr[maxPos])
{
maxPos = i;
}
if (arr[i] < arr[minPos])
{
minPos = i;
}
}
Swap(arr + minSpace,arr + minPos);
if (minSpace == maxPos)
{
maxPos = minPos;
}
Swap(arr + maxSpace,arr + maxPos);
minSpace++;
maxSpace--;
}
}
插入排序:
基本思想
将一个记录插入到已排序好的有序表中,从而得到一个新,记录数增1的有序表。即:先将序列的第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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53//直接插入排序
void InsertSort(int *array, int size)
{
int temp,i,j;
for (i = 1; i < size; i++)
{
temp = array[i];//取出一个未排序的数
for (j = i-1; j >= 0 ;j--) //在排序序列中查找位置
{
if(temp<array[j])
{
array[j + 1] = array[j]; // 向后移动数据
}
else
{
break;
}
}
array[j+1] = temp; //将数据插入
}
}
//优化后的插入排序--折半插入排序
void BinaryInsertSort(int *array,int size)
{
int i, j, left, right, mid;
int key;
for (i = 1; i<size;i++)
{
key = array[i];
left = 0;
right = i - 1;
while (left <= right)
{
mid = left + (right - left);
if (array[mid]<= key)
{
left = mid + 1;
}
else
{
right = mid - 1;
}
}
for (j = i; j>left; j--)
{
array[j] = array[j - 1];
}
array[left] = key;
}
}
希尔排序
1 | //希尔排序 |
堆排序
堆排序:树形选择排序,将带排序记录看成完整的二叉树,第一步:建立初堆,第二步:调整堆
方案一:降序排序,建立小堆
1 | //第二步:调整堆 |
方案二:升序排序,建立大堆
1 | void AdjustDown(int arr[], int size, int root) |
归并排序
思路:利用递归的方法递归划分一个无序数组,直到每个数组只有一个元素时,对相邻的两个数组进行归并。
递归写法
1 | //归并排序 |
非递归写法
1 | void MergeSort(int arr[],int size) |
快速排序
方法一:左右指针法
1 | //左右指针法,选的基准值放在最右边 |
方法二:挖坑法
1 | //挖坑法 |
方法三:前后指针法
1 | //前后指针法 |
快速排序
1 | void _QuickSort(int arr[],int left,int right) |