C语言数组排序技巧在C语言中，数组排序一个常见的操作，用于将一组数据按照特定的顺序（如升序或降序）排列。根据不同的需求和数据规模，可以选择多种排序算法来实现。下面内容是几种常用的数组排序技巧及其特点拓展资料。
一、常见排序技巧拓展资料
| 排序技巧 | 时刻复杂度（平均/最坏） | 空间复杂度 | 是否稳定 | 适用场景 | 说明 |
| 冒泡排序 | O(n2) / O(n2) | O(1) | 是 | 数据量小 | 通过相邻元素比较交换，简单但效率低 |
| 选择排序 | O(n2) / O(n2) | O(1) | 否 | 数据量小 | 每次选出最小元素放在已排序部分末尾 |
| 插入排序 | O(n2) / O(n2) | O(1) | 是 | 数据量小 | 类似整理扑克牌，适合基本有序的数据 |
| 快速排序 | O(n log n) / O(n2) | O(log n) | 否 | 数据量大 | 分治想法，效率高，但不稳定 |
| 归并排序 | O(n log n) / O(n log n) | O(n) | 是 | 数据量大 | 分而治之，稳定性好，适合链表结构 |
| 堆排序 | O(n log n) / O(n log n) | O(1) | 否 | 数据量大 | 利用堆结构进行排序，空间效率高 |
二、常用排序技巧代码示例
1. 冒泡排序
“`c
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;
}
}
“`
2. 快速排序
“`c
void quickSort(int arr[], int low, int high)
if (low < high)
int pivot = partition(arr, low, high);
quickSort(arr, low, pivot – 1);
quickSort(arr, pivot + 1, high);
}
}
int partition(int arr[], int low, int high)
int pivot = arr[high];
int i = low – 1;
for (int j = low; j < high; j++)
if (arr[j] <= pivot)
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
“`
3. 归并排序
“`c
void mergeSort(int arr[], int l, int r)
if (l < r)
int m = l + (r – l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
void merge(int arr[], int l, int m, int r)
int n1 = m – l + 1;
int n2 = r – m;
int left[n1], right[n2];
for (int i = 0; i < n1; i++)
left[i] = arr[l + i];
for (int j = 0; j < n2; j++)
right[j] = arr[m + 1 + j];
int i = 0, j = 0, k = l;
while (i < n1 && j < n2)
if (left[i] <= right[j])
arr[k] = left[i];
i++;
} else
arr[k] = right[j];
j++;
}
k++;
}
while (i < n1)
arr[k] = left[i];
i++;
k++;
}
while (j < n2)
arr[k] = right[j];
j++;
k++;
}
}
“`
三、拓展资料
在实际应用中，应根据数据规模、内存限制以及是否需要稳定性来选择合适的排序算法。对于小型数据集，冒泡、插入等简单排序技巧足够使用；而对于大型数据集，快速排序、归并排序等更高效的算法则更为合适。掌握这些排序技巧不仅有助于进步程序性能，还能加深对算法设计的领会。
