排序算法

排序算法

1、冒泡排序——bubbleSort

冒泡排序是一种简单的比较排序算法。它反复扫描要排序的数组，一次比较相邻的两个元素，如果它们的顺序错误就交换它们。这个过程重复多次，直到整个数组有序。

代码示例：

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
#include <iostream>
using namespace std;

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        for (int j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                // 交换相邻元素
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr)/sizeof(arr[0]);
    bubbleSort(arr, n);
    cout << "排序后的数组: ";
    for (int i=0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
    return 0;
}

另：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int a[101]
int main(){
	int n;
	cin>>n;
	for(int i = 0; i<n; i++)cin>>a[i];
	for(iny j = n-1;j > 0; j--){
		for (int i = 0; i<j; i++){
			if(a[i]>a[i+1]){
				swap(a[i],a[i+1])
			}
		}
	}
	for (int i=0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
    return 0;
}

2、选择排序——selectionSort

选择排序是一种简单而直观的排序算法。它的工作原理是每次从未排序的部分中选出最小的元素，并将其放在已排序部分的末尾。

代码示例：

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
#include <iostream>
using namespace std;

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        int min_idx = i;
        for (int j = i+1; j < n; j++)
            if (arr[j] < arr[min_idx])
                min_idx = j;
        // 交换找到的最小值和当前元素
        int temp = arr[min_idx];
        arr[min_idx] = arr[i];
        arr[i] = temp;
    }
}

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr)/sizeof(arr[0]);
    selectionSort(arr, n);
    cout << "排序后的数组: ";
    for (int i=0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
    return 0;
}

3、插入排序——insertionSort

插入排序是通过构建有序序列来进行排序的，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

代码示例：

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
#include <iostream>
using namespace std;

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        // 向后移动已排序部分的元素以给key腾出位置
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr)/sizeof(arr[0]);
    insertionSort(arr, n);
    cout << "排序后的数组: ";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
    return 0;
}