追梦之旅【数据结构篇】——C语言手撕八大经典排序

**追梦之旅【数据结构篇】——C语言手撕八大经典排序**

在计算机科学领域，排序算法是数据结构中一个非常重要的组成部分。它能够帮助我们对一组数字或字符串进行有序排列，从而更好地处理和分析数据。在本文中，我们将通过手撕八大经典排序算法来深入了解它们的实现原理和优缺点。

###1. 冒泡排序冒泡排序是一种简单的排序算法，它通过反复比较相邻元素并交换他们的位置来达到有序的效果。下面是C语言中的实现代码：

cvoid 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;
 }
 }
 }
}

**时间复杂度:** O(n^2)

**空间复杂度:** O(1)

###2.选择排序选择排序是一种简单的排序算法，它通过在每一趟中找出最小或最大元素并将其放在正确位置来达到有序的效果。下面是C语言中的实现代码：

cvoid 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;
 }
}

**时间复杂度:** O(n^2)

**空间复杂度:** O(1)

###3. 插入排序插入排序是一种简单的排序算法，它通过将每个元素插入到已经有序的列表中来达到有序的效果。下面是C语言中的实现代码：

cvoid 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;
 }
}

**时间复杂度:** O(n^2)

**空间复杂度:** O(1)

###4. 归并排序归并排序是一种分治法的排序算法，它通过将列表分成两半并分别对它们进行排序，然后合并有序的列表来达到有序的效果。下面是C语言中的实现代码：

cvoid mergeSort(int arr[], int l, int r) {
 if (l < r) {
 int mid = (l + r) /2;
 // 递归排序左半部分 mergeSort(arr, l, mid);
 // 递归排序右半部分 mergeSort(arr, mid +1, r);
 // 合并有序的列表 merge(arr, l, mid, r);
 }
}

void merge(int arr[], int l, int m, int r) {
 int n1 = m - l +1;
 int n2 = r - m;
 int L[n1], R[n2];
 for (int i =0; i < n1; i++) {
 L[i] = arr[l + i];
 }
 for (int j =0; j < n2; j++) {
 R[j] = arr[m +1 + j];
 }
 int i =0, j =0, k = l;
 while (i < n1 && j < n2) {
 if (L[i] <= R[j]) {
 // 合并元素 arr[k++] = L[i++];
 } else {
 // 合并元素 arr[k++] = R[j++];
 }
 }
 while (i < n1) {
 // 合并剩余的元素 arr[k++] = L[i++];
 }
 while (j < n2) {
 // 合并剩余的元素 arr[k++] = R[j++];
 }
}

**时间复杂度:** O(n log n)

**空间复杂度:** O(n)

###5. 快速排序快速排序是一种分治法的排序算法，它通过选择一个基准值并将列表分成两半，然后分别对它们进行排序来达到有序的效果。下面是C语言中的实现代码：

cvoid quickSort(int arr[], int l, int r) {
 if (l < r) {
 //选择基准值 int pivot = partition(arr, l, r);
 // 递归排序左半部分 quickSort(arr, l, pivot -1);
 // 递归排序右半部分 quickSort(arr, pivot +1, r);
 }
}

int partition(int arr[], int l, int r) {
 int pivot = arr[r];
 int i = l -1;
 for (int j = l; j < r; j++) {
 if (arr[j] <= pivot) {
 // 交换元素 int temp = arr[i +1];
 arr[i +1] = arr[j];
 arr[j] = temp;
 i++;
 }
 }
 // 交换基准值和最后一个小于基准值的元素 int temp = arr[i +1];
 arr[i +1] = arr[r];
 arr[r] = temp;
 return i +1;
}

**时间复杂度:** O(n log n)

**空间复杂度:** O(log n)

###6. 堆排序堆排序是一种分治法的排序算法，它通过将列表构建成一个最大堆，然后逐步取出根元素并调整堆来达到有序的效果。下面是C语言中的实现代码：

cvoid heapify(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) {
 // 交换元素 int temp = arr[i];
 arr[i] = arr[largest];
 arr[largest] = temp;
 // 递归调整堆 heapify(arr, n, largest);
 }
}

void heapSort(int arr[], int n) {
 for (int i = n /2 -1; i >=0; i--) {
 // 调整堆 heapify(arr, n, i);
 }
 for (int i = n -1; i >0; i--) {
 // 取出根元素并调整堆 int temp = arr[0];
 arr[0] = arr[i];
 arr[i] = temp;
 heapify(arr, i,0);
 }
}

**时间复杂度:** O(n log n)

**空间复杂度:** O(1)

###7. 桶排序桶排序是一种分治法的排序算法，它通过将列表分成多个桶并分别对它们进行排序来达到有序的效果。下面是C语言中的实现代码：

cvoid bucketSort(int arr[], int n) {
 // 创建桶 int buckets[n];
 for (int i =0; i < n; i++) {
 buckets[i] = -1;
 }
 // 将元素放入桶中 for (int i =0; i < n; i++) {
 int index = arr[i];
 if (buckets[index] == -1) {
 buckets[index] = arr[i];
 } else {
 // 找到合适的位置并插入元素 int j = index;
 while (j >=0 && buckets[j] > arr[i]) {
 buckets[j +1] = buckets[j];
 j--;
 }
 buckets[j +1] = arr[i];
 }
 }
 // 将桶中的元素取出并排序