基本排序

选择排序

每次挑最小的放左边

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void selectionSort(int s[], int n)
{
for (int i = 0; i < n-1; ++i)
{
int minIndex = i;
for (int j = i+1; j < n; ++j)
{
if (s[j] < s[minIndex])
{
minIndex = j;
}
}
swap(s[i], s[minIndex]);
}
}

插入排序

从左往右遍历,取出当前元素有序地插到其左半部分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void insertionSort(int s[], int n)
{
for (int i = 1; i < n; ++i)
{
for (int j = i; j >= 1; --j)
{
if (s[j] < s[j-1])
{
swap(s[j], s[j-1]);
}
else
{
break;
}
}
}
}

冒泡排序

从左往右进行两两比较,每一趟可以使最大值在最右边

1
2
3
4
5
6
7
8
9
10
11
12
13
void bubbleSort(int s[], int n)
{
for (int i = n-1; i > 0; --i)
{
for (int j = 0; j < i; ++j)
{
if (s[j] > s[j+1])
{
swap(s[j], s[j+1]);
}
}
}
}

改进冒泡排序:优化外层循环

如果某一趟比较没有数值交换,则说明已经排好序;处理在排序过程中数组整体已经有序的情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void bubbleSort2(int s[], int n)
{
for (int i = n-1; i > 0; --i)
{
bool isSorted = true;

for (int j = 0; j < i; ++j)
{
if (s[j] > s[j+1])
{
swap(s[j], s[j+1]);
isSorted = false;
}
}

if (isSorted)
{
return;
}
}
}

改进冒泡排序:优化内层循环

每一趟遍历记录最后一次交换的位置,这个位置后的元素其实都是有序的,不需要再次比较

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void bubbleSort3(int s[], int n)
{
int endPos = n-1;
for (int i = n-1; i > 0; --i)
{
int lastExchangeIndex = 0;
for (int j = 0; j < endPos; ++j)
{
if (s[j] > s[j+1])
{
swap(s[j], s[j+1]);
lastExchangeIndex = j;
}
}

endPos = lastExchangeIndex;
}
}
  1. 选择排序
  2. 插入排序
  3. 冒泡排序
  4. 改进冒泡排序:优化外层循环
  5. 改进冒泡排序:优化内层循环