选择排序
每次挑最小的放左边
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; } }
|