排序算法代码

排序算法是计算机科学中的一个重要领域，它涉及到如何对一组数据进行排序。排序算法使用不同的方法来对数据进行排序，包括比较排序、非比较排序、序列排序和分布排序等。在本文中，我们将从多个角度分析排序算法代码，探讨如何实现不同类型的排序算法。

比较排序算法

比较排序算法通过比较数据元素的大小来进行排序。其中，最常见和最基本的算法是冒泡排序、插入排序和选择排序。这些算法通常是最简单、最直接的排序方法，但它们的时间复杂度并不理想，因为它们需要对每个元素进行比较和移动。下面是三种算法的示例代码：

冒泡排序：

```

void bubbleSort(int arr[], int n) {

int i, j;

bool swapped;

for (i = 0; i < n-1; i++) {

swapped = false;

for (j = 0; j < n-i-1; j++) {

if (arr[j] > arr[j+1]) {

swap(&arr[j], &arr[j+1]);

swapped = true;

}

}

if (swapped == false) break;

}

}

```

插入排序：

```

void insertionSort(int arr[], int n) {

int i, key, j;

for (i = 1; i < n; i++) {

key = arr[i];

j = i - 1;

while (j >= 0 && arr[j] > key) {

arr[j+1] = arr[j];

j = j - 1;

}

arr[j+1] = key;

}

}

```

选择排序：

```

void selectionSort(int arr[], int n) {

int i, j, min_idx;

for (i = 0; i < n-1; i++) {

min_idx = i;

for (j = i+1; j < n; j++) {

if (arr[j] < arr[min_idx])

min_idx = j;

}

swap(&arr[min_idx], &arr[i]);

}

}

```

非比较排序算法

非比较排序算法不使用比较操作来排序数据，而是利用各种数材结构如哈希表、计数排序和基数排序等。与比较排序算法相比，非比较排序算法的时间复杂度通常更短，但空间复杂度则更高。以下是几种非比较排序算法的示例代码：

计数排序：

```

void countSort(int arr[], int n) {

int max = arr[0];

for (int i = 1; i < n; i++) {

if (arr[i] > max)

max = arr[i];

}

int count[max+1] = {0};

for (int i = 0; i < n; i++) {

count[arr[i]]++;

}

for (int i = 1; i <= max; i++) {

count[i] += count[i-1];

}

int output[n];

for (int i = n-1; i >= 0; i--) {

output[count[arr[i]]-1] = arr[i];

count[arr[i]]--;

}

for (int i = 0; i < n; i++) {

arr[i] = output[i];

}

}

```

基数排序：

```

void radixSort(int arr[], int n) {

int bucket[10][10], bucket_count[10];

int max_value = arr[0];

for (int i = 1; i < n; i++) {

if (arr[i] > max_value)

max_value = arr[i];

}

int digit = 0;

while (max_value > 0) {

max_value /= 10;

digit++;

}

int base = 1;

for (int i = 0; i < digit; i++) {

for (int j = 0; j < 10; j++) {

bucket_count[j] = 0;

}

for (int j = 0; j < n; j++) {

int tmp = (arr[j] / base) % 10;

bucket[tmp][bucket_count[tmp]] = arr[j];

bucket_count[tmp]++;

}

int k = 0;

for (int j = 0; j < 10; j++) {

for (int l = 0; l < bucket_count[j]; l++) {

arr[k++] = bucket[j][l];

}

}

base *= 10;

}

}

```

序列排序算法

序列排序算法是一种直接在数据元素之间执行排序的方法，因此它比比较排序算法更容易实现，并且通常比非比较排序算法更快。其中最著名的方法是快速排序和归并排序。以下是这两种算法的示例代码：

快速排序：

```

void quickSort(int arr[], int low, int high) {

if (low < high) {

int pi = partition(arr, low, high);

quickSort(arr, low, pi-1);

quickSort(arr, pi+1, high);

}

}

int partition(int arr[], int low, int high) {

int pivot = arr[high];

int i = low - 1;

for (int j = low; j <= high-1; j++) {

if (arr[j] < pivot) {

i++;

swap(&arr[i], &arr[j]);

}

}

swap(&arr[i+1], &arr[high]);

return (i+1);

}

```

归并排序：

```

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 i, j, k;

int n1 = m - l + 1;

int n2 = r - m;

int L[n1], R[n2];

for (i = 0; i < n1; i++)

L[i] = arr[l + i];

for (j = 0; j < n2; j++)

R[j] = arr[m + 1 + j];

i = 0;

j = 0;

k = l;

while (i < n1 && j < n2) {

if (L[i] <= R[j]) {

arr[k] = L[i];

i++;

}

else {

arr[k] = R[j];

j++;

}

k++;

}

while (i < n1) {

arr[k] = L[i];

i++;

k++;

}

while (j < n2) {

arr[k] = R[j];

j++;

k++;

}

}

```

分布排序算法

分布排序算法是一组不同的算法，它们使用一些特定的分布属性来实现排序，其中最著名的算法是桶排序。以下是桶排序的示例代码：

桶排序：

```

void bucketSort(int arr[], int n) {

int i, j;

int min_value = arr[0], max_value = arr[0];

for (i = 1; i < n; i++) {

if (arr[i] < min_value) min_value = arr[i];

if (arr[i] > max_value) max_value = arr[i];

}

int bucket_count = (max_value-min_value) / 5 + 1;

vector bucket[bucket_count];

for (i = 0; i < n; i++) {

bucket[(arr[i]-min_value)/5].push_back(arr[i]);

}

int k = 0;

for (i = 0; i < bucket_count; i++) {

sort(bucket[i].begin(), bucket[i].end());

for (j = 0; j < bucket[i].size(); j++) {

arr[k++] = bucket[i][j];

}

}

}

```

结论

本文从比较和非比较排序算法、序列排序算法以及分布排序算法三个角度分析了排序算法代码，其中包括冒泡排序、插入排序、选择排序、计数排序、基数排序、快速排序、归并排序和桶排序等算法。每个算法都有其优缺点，可以根据具体情况选择不同的算法。本文为读者提供了实现不同排序算法的示例代码，供读者参考。