冒泡排序
基本思想：对所有相邻记录的关键字值进行比效，如果是逆顺（a[j]>a[j+1]），则将其交换，最终达到有序化。
假定arr[]={ 28,15,75,39,81,20,96,138 };
下图显示了第一次内循环过程：
代码实现：
int main() {
//给定一个数组
int arr[] = { 28,15,75,39,81,20,96,138 };
//加强for循环
cout << "原数组为：" << endl;
for (int i : arr) {
cout << i << " ";
}
bubble_sort(arr,sizeof(arr) / sizeof(int));
cout << "\n新数组为：" << endl;
for (int i : arr) {
cout << i << " ";
}
}
void bubble_sort(int arr[], int n) {
bool flag;//判断
for (int i = 0; i < n; i++) {
flag = false;
//每进行一次，末尾就要减一
for (int j = 0; j < n-i-1; j++) {
//判断是否可以交换，并标记flag
if (arr[j] > arr[j + 1]) {
int temp = 0;
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
flag = true;
}
}
//当排好顺序后，判断flag跳出循环
if (!flag) {
break;
}
}
}
运行结果：
插入排序
基本思想：将整个数组a分为有序和无序的两个部分。前者在左边，后者在右边。开始有序的部分只有a[0] , 其余都属于无序的部分。每次取出无序部分的第一个（最左边）元素，把它加入有序部分。假设插入合适的位置p，则原p位置及其后面的有序部分元素都向右移动一个位置，有序的部分即增加了一个元素。一直做下去，直到无序的部分没有元素。
假定arr[]={ 28,15,75,39,81,20,96,138 };
下图表示了插入的过程：
代码实现：
int main() {
//给定一个数组
int arr[] = { 28,15,75,39,81,20,96,138 };
//加强for循环
cout << "原数组为：" << endl;
for (int i : arr) {
cout << i << " ";
}
insertion_sort(arr,sizeof(arr) / sizeof(int));
cout << "\n新数组为：" << endl;
for (int i : arr) {
cout << i << " ";
}
}
void insertion_sort(int arr[], int n) {
for (int i = 0; i < n; i++) {
//从已知有序元素中从后往前扫描，将无序中大的元素插入到有序元素中
for (int j=i; j > 0 && arr[j-1] > arr[j]; j--) {
int temp = 0;
temp = arr[j-1];
arr[j-1] = arr[j];
arr[j] = temp;
}
}
}
运行结果：
选择排序
基本思想：每次从待排序列中选出一个最小值，然后放在序列的起始位置，直到全部待排数据排完即可。
代码实现：
int main() {
//给定一个数组
int arr[] = { 28,15,75,39,81,20,96,138 };
//加强for循环
cout << "原数组为：" << endl;
for (int i : arr) {
cout << i << " ";
}
insertion_sort(arr,sizeof(arr) / sizeof(int));
cout << "\n新数组为：" << endl;
for (int i : arr) {
cout << i << " ";
}
}
void selection_sort(int arr[], int n) {
//标记最小值下标
int mid = 0;
for (int i = 0; i < n; i++) {
mid = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[mid]) {
mid = j;
}
}
int temp = 0;
temp = arr[mid];
arr[mid] = arr[i];
arr[i] = temp;
}
}
运行结果：
