排序小结
排序算法是基础之基础。在这里小结一下。方便自己查阅和学习。
1.冒泡排序(BubbleSort)
思想：比较相邻的两个元素，如果前面的元素大于后面的元素，交换之。
思路：采用双层循环。外循环控制要处理多少趟。里面循环用来做元素的交换操作。注意上下界。
稳定性：稳定
时间复杂度：O(n2)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
void
bubbleSort(
int
a[],
int
size)
{
int
tmp;
for
(
int
i = 0; i < size; i++)
{
//每一趟都会把最大的元素放入最右边的位置
//最右边的位置会一点点往左移动
for
(
int
j = 0; j < size - i - 1; j++)
{
if
(a[j] > a[j + 1])
{
tmp = a[j];
a[j] = a[j + 1];
a[j + 1] = tmp;
}
}
}
}
|
2.快速排序(quickSort)
思想：找到第一个元素的最终位置，然后对数组进行分割，对左边的进行快排，对右边的进行快排。
思路：采用递归，需要一个辅助函数findPos()来找到某一个元素的最终位置。
稳定性：不稳定
时间复杂度：有时O(nlogn),最坏情况是已经排好序，这样时间复杂度为O(n2)
伪算法
/*
* 快速排序（伪算法） 2016-08-14 11:01:34
* 1.先找到第一个元素的最终位置
* 2.对第一个元素的最终位置之前的元素，进行快速排序。
* 3.对第一个元素的最终位置之后的元素，进行快速排序。
*
*/
|
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
|
int
findPos(
int
a[],
int
low,
int
high)
{
int
val = a[low];
while
(low < high)
{
//因为val取的是最前面的值，所以先从后往前遍历比较
while
(low < high && a[high] >= val)
high--;
a[low] = a[high];
//将后面较小值赋值给前面已经做好备份的位置上
//然后从前往后遍历比较
while
(low < high && a[low] <= val)
low++;
a[high] = a[low];
//将前面较大值赋值给后面已经做好备份的位置上
}
a[low] = val;
return
low;
}
void
quickSort(
int
a[],
int
low,
int
high)
{
if
(low < high)
{
int
pos = findPos(a,low,high);
quickSort(a,low,pos-1);
quickSort(a,pos+1,high);
}
}
|
3.直接插入排序(insertSort)也叫选择插入排序
思想：将第i个元素插入到前面i-1个已排好序的记录中。直到所有的元素都排一次。
思路：见伪算法
稳定性：稳定
时间复杂度：O(n2)
伪算法
/*
* 插入排序（伪算法） 2016-08-14 12:23:09
* 1. 将相邻的两个元素比较，如果前面的数大于后面的数，则交换。
* 直到找到前面的数小于后面的，就把这个值插入到这个位置。
* 2. 循环1，直到所有的元素都有序排列。
*
*/
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
void
insertSort(
int
a[],
int
size)
{
int
i, j, tmp;
for
(i = 0; i < size; i++)
{
tmp = a[i];
for
(j = i - 1; j >= 0 && a[j] > tmp; j--)
{
a[j+1] = a[j];
}
a[j + 1] = tmp;
}
}
|
4.选择排序(selectSort)
思想：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在待序列的起始位置。
思路：见伪算法
稳定性：不稳定
时间复杂度：O(n2)
伪算法
/*
* 选择排序（伪算法） 2016-08-14 13:08:50
* 1. 工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在待序列的起始位置。
* 2. 循环1，直到全部待排序的数据元素排完。
*
*/
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
void
selectSort(
int
a[],
int
size)
{
int
currentSmallIndex;
//记录待排序队列中最小元素的下标
int
tmp;
//记录最小元素的大小
for
(
int
i = 0; i < size; i++)
{
tmp = a[i];
currentSmallIndex = i;
for
(
int
j = i + 1; j < size; j++)
{
if
(a[j] < tmp)
{
currentSmallIndex = j;
tmp = a[j];
}
}
a[currentSmallIndex] = a[i];
a[i] = tmp;
}
}
|
5.归并排序(mergeSort)
思想：将数组递归分成2半，知道数组的长度为1，然后将分成2半的数组合并。
思路：需要使用辅助函数merge()来合并
稳定性：稳定
时间复杂度：O(n2)
伪算法
/*
1.将数组分成左右两半
2.递归1，直道只剩1个元素的时候，然后合并。
*/
|
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
|
void
merge(
int
a[],
int
start,
int
end)
{
int
mid = (start + end) / 2;
int
left, right;
int
* temp =
new
int
[end - start + 1];
int
k = 0;
//临时数组的下标
left = start;
right = mid + 1;
while
(left <= mid && right <= end)
{
while
((left <= mid && right <= end) && (a[left] < a[right]))
temp[k++] = a[left++];
while
((left <= mid && right <= end) && (a[right] < a[left]))
temp[k++] = a[right++];
}
while
(left <= mid)
temp[k++] = a[left++];
while
(right <= end)
temp[k++] = a[right++];
//将临时数组中的元素，找到原数组的位置，按位赋值过去。
//这里需要注意原数组的起始位置是start，而不是0
for
(
int
i = start, k = 0; i <= end; i++, k++)
a[i] = temp[k];
delete
[] temp;
}
void
mergeSort(
int
a[],
int
start,
int
end)
{
if
(start < end)
{
int
mid = (start + end) / 2;
mergeSort(a, start, mid);
//左数组合并排序
mergeSort(a, mid + 1, end);
//右数组合并排序
merge(a, start, end);
//整体排序
}
}
|
排序总结未完待续。
