算法0.1排序算法

数组排序是计算机科学中的一个基本问题，有许多经典的排序算法。每种算法都有其特点和适用场景。以下是一些常见的排序算法及其简要说明：

1 . 冒泡排序（Bubble Sort）

  • 原理：重复遍历数组，比较相邻元素并交换位置，直到数组有序。
  • 时间复杂度：平均和最坏情况为 (O(n^2))，最好情况为 (O(n))。
  • 稳定性：稳定。

2 . 选择排序（Selection Sort）

  • 原理：每次从未排序的部分选择最小（或最大）的元素，放到已排序部分的末尾。
  • 时间复杂度：平均和最坏情况为 (O(n^2))。
  • 稳定性：不稳定。

3 . 插入排序（Insertion Sort）

  • 原理：将每个新元素插入到已排序部分的适当位置。
  • 时间复杂度：平均和最坏情况为 (O(n^2))，最好情况为 (O(n))。
  • 稳定性：稳定。

3.1 希尔排序（Shell Sort）

  • 原理：先将数组分割成若干子序列，然后对子序列进行插入排序，使得子序列基本有序，然后逐渐缩小子序列的规模，直到整个数组有序。
  • 时间复杂度：平均和最坏情况为 (O(n^2))，最好情况为 (O(n))。

4 . 快速排序（Quick Sort）

  • 原理：通过一个划分操作将数组分成两部分，递归地对这两部分进行排序。
  • 时间复杂度：平均情况为 (O(n \log n))，最坏情况为 (O(n^2))。
  • 稳定性：不稳定。

5 . 归并排序（Merge Sort）

  • 原理：将数组分成两部分，递归地对这两部分进行排序，然后合并成一个有序数组。
  • 时间复杂度：平均和最坏情况均为 (O(n \log n))。
  • 稳定性：稳定。

6 . 堆排序（Heap Sort）

  • 原理：利用堆数据结构进行排序，首先构建一个最大堆（或最小堆），然后逐个取出堆顶元素。
  • 时间复杂度：平均和最坏情况均为 (O(n \log n))。
  • 稳定性：不稳定。

7 . 计数排序（Counting Sort）

  • 原理：适用于范围较小的整数排序，通过计数每个元素出现的次数，然后根据计数结果构造有序数组。
  • 时间复杂度：(O(n + k))，其中 (k) 是元素的范围。
  • 稳定性：稳定。

8 . 桶排序（Bucket Sort）

  • 原理：将数组中的元素分布到多个桶中，每个桶再分别排序（可以使用其他排序算法）。
  • 时间复杂度：平均情况为 (O(n + k))，其中 (k) 是桶的数量。
  • 稳定性：稳定。

9 . 基数排序（Radix Sort）

  • 原理：通过按位排序，先按最低有效位排序，然后依次按更高位排序。
  • 时间复杂度：(O(nk))，其中 (k) 是数字的最大位数。
  • 稳定性：稳定。

10 示例代码

以下是几种常见排序算法的示例代码：

10.1 冒泡排序（交换）

1
2
3
4
5
6
7
8
9
10
11
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;
            }
        }
    }
}

10.2 选择排序（交换）

1
2
3
4
5
6
7
8
9
10
11
12
13
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;
    }
}

10.3 插入排序（推移）

1
2
3
4
5
6
7
8
9
10
11
void 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 = j - 1;
        }
        arr[j + 1] = key;
    }
}
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
27
28
29
30
31
32
33
//核心思想：划分为以排序和为排序逐步将为排序的转为以排序的。
//假设0以排序，排列引索1到n次。
//记录要移动的元素引索和值，逐步与i-1到0个元素比较。在比较的过程中将不符合要求的值向后推移并记录每次的引索值。设置结束条件为到0且该元素的值大于记录的初始值。
//将记录的初始值付给记录的引索对应的元素。


int main()
{
    int a[10]= {1,3,4,5,2,3,6,7,1,3};
    int i=0;
    int j=0;
    int index = 0;
    int temp = 0;
    for(i=1;i<10;i++)
    {
        temp = a[i];
        index = i;
        for(j=i-1;j>=0&&temp<a[j];j--)
        {
                index = j;
                a[j+1]= a[j];
        }
        
        a[index] = temp;
        for(int k = 0; k < 10; k++)
        {
            printf("%d ", a[k]);
        }  
        printf("\n");
    }

    return 0;
}

10.4 希尔排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void shellSort(int arr[], int n)
{
    int temp = 0;
    int i=0;
    int j = 0;
    int z = 0;
    for(z =n/2;z>0;z = z/2)
    {
        for(i=z;i<n;i++)
        {
            temp = arr[i];
            for (j = i; j >= z && arr[j-z] > temp; j-=z)
            {
                arr[j]=arr[j-z];
            }
            arr[j] = temp;
        }
    }

}

10.5 快速排序

双指针法实现快速排序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 先初始化两个指针一个prev和cur，一个基准值keyi，prev指向数组的第一个元素，cur指向数组的第二个元素。如果cur指向的小于kyei则++prev然后与prev所指元素交换，然后++cur。如果cur指向的大于kyei则直接++cur。如果cur指向了最后一个元素 ，则将prev所指元素与基准值keyi交换。并以prev为中心重新递归两边。
void QuickSortD(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}

	int keyi = begin;
	int prev = begin;
	int cur = begin + 1;
	while (cur <= end)
	{
		if (a[cur] < a[keyi] && ++prev != cur)
		{
			Swap(&a[cur], &a[prev]);
		}
		cur++;
	}
	Swap(&a[keyi], &a[prev]);
	QuickSortD(a, begin, prev - 1);
	QuickSortD(a, prev + 1, end);
}

10.6 归并排序

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
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 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];
            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++;
    }
}