排序算法

我也还在学， 慢慢更新嘿嘿

1、冒泡排序

冒泡排序是指每一次遍历时都将最大的数放置在最后面，像一个气泡浮到了水面，故称冒泡排序

for (int i = 0; i < n; i++)
{
	for (int j = 0; j < n - i - 1; j++)
	{
		if (a[j] > a[j + 1])
		{
			int tmp = a[j];
			a[j] = a[j + 1];
			a[j + 1] = tmp;
		}
	}
}

2、选择排序

选择排序是每一次遍历（第n次）都将最大（最小）的数与第n位的数对调，达到排序的目的

#include<stdio.h>

void InsertSort(int*, int);
int findMin(int*, int, int);
void outputData(int*, int);


int main()
{
    int n;
    scanf("%d", &n);
    int a[n];
    int i;
    for (i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
    }
    InsertSort(a, n);
    return 0;
}

void InsertSort(int a[],int n)
{
    int i;
    for (i = 0; i < n - 1; i++)
    {
        int tmp = a[i];
        int min = findMin(a, i, n);
        a[i] = a[min];
        a[min] = tmp;
        outputData(a, n);
    }
}

int findMin(int data[], int startLoc, int endLoc)
{
    int i, xiabiao = startLoc;
    int min = data[startLoc];
    for (i = startLoc; i < endLoc; i++)
    {
        if (data[i] < min)
        {
            min = data[i];
            xiabiao = i;
        }
    }
    return xiabiao;
}

void outputData(int data[],int elementCount)
{
    int i = 0;
    for (i = 0; i < elementCount; i++)
    {
        printf("%d ", data[i]);
    }
    printf("\n");
}

3、插入排序

插入排序算法描述如下：
初始序列：49 38 65 97 76 13 27 49
将元素(38) 插入合适位置： [38 49] 65 97 76 13 27 49
将元素(65) 插入合适位置： [38 49 65] 97 76 13 27 49
将元素(97) 插入合适位置： [38 49 65 97] 76 13 27 49
将元素(76) 插入合适位置： [38 49 65 76 97] 13 27 49
将元素(13) 插入合适位置： [13 38 49 65 76 97] 27 49
将元素(27) 插入合适位置： [13 27 38 49 65 76 97] 49
将元素(49) 插入合适位置： [13 27 38 49 49 65 76 97]

#include<stdio.h>

void InsertSort(int*, int);
void printArray(int*, int);

int main()
{
    int n;
    scanf("%d", &n);
    int a[n];
    int i;
    for (i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
    }
    InsertSort(a, n);
    return 0;
}

void InsertSort(int a[],int n)
{
    int i, j, tmp;
    for (i = 1; i < n; i++)
    {
        tmp = a[i];
        j = i - 1;
        while (tmp < a[j])
        {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = tmp;
        printArray(a, n);
    }
}

void printArray(int a[],int n)
{
    int i;
    for (i = 0; i < n; i++)
    {
        printf("%d ", a[i]);
    }
    printf("\n");
    return;
}

4、快速排序

例题：来自洛谷

https://www.luogu.com.cn/problem/P1177

#include <stdio.h>

void myqsort(int l, int r);

int a[1000001];

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
    }
    myqsort(0, n - 1);
    for (int i = 0; i < n; i++)
    {
        printf("%d ", a[i]);
    }
    return 0;
}

void myqsort(int l, int r)
{
    int key = a[(l + r) / 2];
    int i = l, j = r;
    while (i <= j)
    {
        while (a[i] < key)
        {
            i++;
        }
        while (a[j] > key)
        {
            j--;
        }
        if (i <= j)
        {
            int tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
            i++;
            j--;
        }
    }
    if (l < j)
    {
        myqsort(l, j);
    }
    if (i < r)
    {
        myqsort(i, r);
    }
}

5、桶排序

例题：来自洛谷

https://www.luogu.com.cn/problem/P1059

#include <stdio.h>

int main()
{
    int x[10001] = {0};
    int n, num;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &num);
        x[num]++;
    }
    for (int i = 0; i < 10001; i++)
    {
        for (int j = 0; j < x[i]; j++)
        {
            printf("%d ", i);
        }
    }
    return 0;
}

6、堆排序

7、归并排序

8、希尔排序

9、基数排序

10、对超大数据（几百位）的排序

例题：来自洛谷

https://www.luogu.com.cn/problem/P1781

使用字符串储存，通过比较长度（strlen）和比较字典顺序（strcmp）来进行比较排序