十大排序算法【原理】【步骤】【动图】【C++实现】

**十大排序算法**

排序算法是计算机科学中一个非常重要的概念，它们用于将数据按一定顺序排列，使得数据变得有序、可管理。以下是十大排序算法的原理、步骤、动图和C++实现。

###1. 冒泡排序**原理:** 冒泡排序是一种简单的交换排序算法，它通过反复地遍历列表，相邻元素之间进行比较，如果两个相邻元素的顺序错误，则将它们交换位置，以此达到让数据有序的目的。

**步骤:**

1. 从头到尾遍历列表。
2. 如果当前元素与下一个元素的顺序错误，则交换他们。
3. 重复步骤1 和2，直到列表有序。

**动图:** [冒泡排序动画]( />
**C++实现:**

cppvoid 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]) {
 // 交换 arr[j] 和 arr[j +1]
 int temp = arr[j];
 arr[j] = arr[j +1];
 arr[j +1] = temp;
 }
 }
 }
}

###2.选择排序**原理:**选择排序是一种简单的交换排序算法，它通过反复地遍历列表，找出最小或最大元素，并将其放在列表的起始位置。

**步骤:**

1. 从头到尾遍历列表。
2. 找出当前元素与其他元素之间的最小或最大值，并交换它们。
3. 重复步骤1 和2，直到列表有序。

**动图:** [选择排序动画]( />
**C++实现:**

cppvoid selectionSort(int arr[], int n) {
 for (int i =0; i < n -1; i++) {
 int minIndex = i;
 for (int j = i +1; j < n; j++) {
 if (arr[j] < arr[minIndex]) {
 // 更新最小值索引 minIndex = j;
 }
 }
 // 交换 arr[i] 和 arr[minIndex]
 int temp = arr[i];
 arr[i] = arr[minIndex];
 arr[minIndex] = temp;
 }
}

###3. 插入排序**原理:** 插入排序是一种简单的交换排序算法，它通过反复地遍历列表，找到每个元素的正确位置，并将其插入到该位置。

**步骤:**

1. 从头到尾遍历列表。
2. 找出当前元素的正确位置，并将其插入到该位置。
3. 重复步骤1 和2，直到列表有序。

**动图:** [插入排序动画]( />
**C++实现:**

cppvoid insertionSort(int arr[], int n) {
 for (int i =1; i < n; i++) {
 int key = arr[i];
 int j = i -1;
 while (j >=0 && arr[j] > key) {
 // 移动元素 arr[j +1] = arr[j];
 j--;
 }
 // 插入元素 arr[j +1] = key;
 }
}

###4. 归并排序**原理:** 归并排序是一种分治法的排序算法，它通过反复地将列表分成两半，并对每半进行归并，直到列表有序。

**步骤:**

1. 将列表分成两半。
2. 对每半进行归并。
3. 重复步骤1 和2，直到列表有序。

**动图:** [归并排序动画]( />
**C++实现:**

cppvoid mergeSort(int arr[], int n) {
 if (n <=1) return;
 int mid = n /2;
 // 分成两半 int left[mid];
 int right[n - mid];
 for (int i =0; i < mid; i++) {
 left[i] = arr[i];
 }
 for (int i = mid; i < n; i++) {
 right[i - mid] = arr[i];
 }
 // 归并 merge(left, right, arr);
}

void merge(int left[], int right[], int arr[]) {
 int i =0;
 int j =0;
 int k =0;
 while (i < sizeof(left) && j < sizeof(right)) {
 if (left[i] <= right[j]) {
 arr[k++] = left[i++];
 } else {
 arr[k++] = right[j++];
 }
 }
 // 将剩余元素复制到 arr 中 while (i < sizeof(left)) {
 arr[k++] = left[i++];
 }
 while (j < sizeof(right)) {
 arr[k++] = right[j++];
 }
}

###5. 快速排序**原理:** 快速排序是一种分治法的排序算法，它通过反复地将列表分成两半，并对每半进行快速排序，直到列表有序。

**步骤:**

1. 将列表分成两半。
2. 对每半进行快速排序。
3. 重复步骤1 和2，直到列表有序。

**动图:** [快速排序动画]( />
**C++实现:**

cppvoid quickSort(int arr[], int n) {
 if (n <=1) return;
 int pivot = arr[0];
 int left[n -1];
 int right[n -1];
 for (int i =1; i < n; i++) {
 if (arr[i] <= pivot) {
 // 将小于等于 pivot 的元素放入左半 left[i -1] = arr[i];
 } else {
 // 将大于 pivot 的元素放入右半 right[i -1] = arr[i];
 }
 }
 // 对左半进行快速排序 quickSort(left, n -1);
 // 对右半进行快速排序 quickSort(right, n -1);
}

###6. 堆排序**原理:** 堆排序是一种分治法的排序算法，它通过反复地将列表分成两半，并对每半进行堆化，直到列表有序。

**步骤:**

1. 将列表分成两半。
2. 对每半进行堆化。
3. 重复步骤1 和2，直到列表有序。

**动图:** [堆排序动画]( />
**C++实现:**

cppvoid heapify(int arr[], int n) {
 for (int i = n /2; i >=0; i--) {
 // 堆化 arr[i] 到 arr[0]
 heapifyHelper(arr, n, i);
 }
}

void heapifyHelper(int arr[], int n, int i) {
 int largest = i;
 int left =2 * i +1;
 int right =2 * i +2;
 if (left < n && arr[left] > arr[largest]) {
 // 更新最大值索引 largest = left;
 }
 if (right < n && arr[right] > arr[largest]) {
 // 更新最大值索引 largest = right;
 }
 if (largest != i) {
 // 交换 arr[i] 和 arr[largest]
 int temp = arr[i];
 arr[i] = arr[largest];
 arr[largest] = temp;
 // 堆化 arr[largest]
 heapifyHelper(arr, n, largest);
 }
}

void heapSort(int arr[], int n) {
 heapify(arr, n);
 for (int i = n -1; i >=0; i--) {
 // 交换 arr[0] 和 arr[i]
 int temp = arr[0];
 arr[0] = arr[i];
 arr[i] = temp;
 // 堆化 arr[0]
 heapifyHelper(arr, i,0);
 }
}

###7. 桶排序**原理