C语言3种常用的排序方法_c语言排序的三种方法

c语言4种常用的排序方法

1.冒泡法排序

冒泡排序是最简单的排序方法：原理是：从左到右，相邻元素进行比较。每次比较一轮，就会找到序列中最大的一个或最小的一个。这个数就会从序列的最右边冒出来。

#include<stdio.h>
int main()
{
	int i,j,t,a[20];
	printf("输入20个整数：\n");
	for(i=0;i<=10;i++)
		scanf("%d",&a[i]);
	for(i=0;i<=20;i++)				
		for(j=0;j<=20-i;j++)
			if(a[j]>a[j+1])			
			{
				t=a[j];
				a[j]=a[j+1];
				a[j+1]=t;
			}
	for(i=0;i<20;i++)
		printf("%5d",a[i]);
	printf("\n");
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

2.选择法排序

思路是设有10个元素a[1]-a[10]，将a[1]与a[2]-a[10]比较，若a[1]比a[2]-a[10]都小，则不进行交换。若a[2]-a[10]中有一个以上比a[1]小，则将其中最大的一个与a[1]交换，此时a[1]就存放了10个数中最小的一个。同理，第二轮拿a[2]与a[3]-a[10]比较，a[2]存放a[2]-a[10]中最小的数，以此类推。

#include<stdio.h>
int main()
{
	int i,j,t,a[20];
	printf("请输入20个整数：\n");
	for(i=0;i<20;i++)
		scanf("%d",&a[i]);    //输入20个整数存到数组里
	for(i=0;i<=20;i++)
		for(j=i+1;j<20;j++)
			if(a[i]>a[j])     //如果前一个数比后一个大，则调换值
			{
				t=a[i];
				a[i]=a[j];
				a[j]=t;
			}
	for(i=0;i<20;i++)
		printf("%d",a[i]);
	printf("\n");
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

3.插入法排序

插入排序是一种简单直观的排序算法，适用于小规模数据或者部分有序的数据。下面是C语言中插入排序的原理：

插入排序的原理是将一个待排序的元素插入到已排好序的序列中的正确位置。具体步骤如下：

1. 假设待排序的序列为arr，序列的第一个元素arr[0]默认已经是有序的。

2. 从第二个元素arr[1]开始，依次将每个元素插入到前面已排好序的序列中。

3. 对于第i个元素（i从1开始），将其与前面已排序的元素进行比较。如果前面的元素较大，则将其后移一位，直到找到合适的位置插入。

4. 重复步骤3，直到将所有的元素都插入到正确的位置。

下面是C语言中插入排序的示例代码：

void insertionSort(int arr[], int n) {
    int i, j, key;
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;

        // 将比key大的元素向后移动
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }

        // 将key插入到正确的位置
        arr[j + 1] = key;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

在这段代码中，我们使用了一个嵌套的循环进行元素的比较和后移操作。外层循环遍历待排序的元素，内层循环比较当前元素与已排序的元素，将较大的元素后移一位，直到找到合适的位置插入。

插入排序的时间复杂度为O(n^2)，其中n是序列的长度。尽管插入排序的时间复杂度较高，但在处理小规模数据或者部分有序的数据时，插入排序是一种简单且高效的排序算法。

4.快速排序

快速排序（Quick Sort）是一种常见且高效的排序算法，其原理基于分治思想。

快速排序的原理如下：

1. 选择一个基准元素（pivot）。常用的选择方式是取序列的第一个元素。

2. 将序列分为两部分，所有小于基准元素的元素放在基准元素的左边，所有大于基准元素的元素放在基准元素的右边。

3. 对左右两个子序列递归地进行快速排序。

4. 递归的终止条件是子序列的长度为0或1，此时子序列已经有序。

5. 将左子序列、基准元素和右子序列按顺序合并，得到有序的序列。

下面是C语言中快速排序的示例代码：

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        // 选择基准元素
        int pivot = arr[low];
        int i = low;
        int j = high;

        while (i < j) {
            // 从右向左找到第一个小于基准元素的元素
            while (i < j && arr[j] >= pivot) {
                j--;
            }
            if (i < j) {
                arr[i++] = arr[j];
            }

            // 从左向右找到第一个大于基准元素的元素
            while (i < j && arr[i] <= pivot) {
                i++;
            }
            if (i < j) {
                arr[j--] = arr[i];
            }
        }

        // 将基准元素放到正确的位置
        arr[i] = pivot;

        // 递归地对左右两个子序列进行快速排序
        quickSort(arr, low, i - 1);
        quickSort(arr, i + 1, high);
    }
}
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。

快速排序的平均时间复杂度为O(nlogn)，在大多数情况下具有较高的效率。然而，在最坏情况下，快速排序的时间复杂度为O(n^2)，为了避免最坏情况的发生，可以采用随机选取基准元素的方式。