3种排序算法

冒泡排序(Bubble Sort)

主要思想

冒泡排序是一种简单的排序算法，它可以将一组元素从小到大或从大到小排列。它的主要思想是通过重复地比较相邻的两个元素来排序，如果第一个元素比第二个元素大(或第一个元素比第二个元素小)，则交换它们的位置。然后又比较一次下一对元素，重复这个过程，直到最后一对元素则完成排序。

在冒泡排序的过程中，比较次数是一个相对比较固定的值，要将所有元素排序，至少要进行n-1次比较(共有n个元素)，最多要进行n^2/2次比较，因此冒泡排序的时间复杂度是O(N^2)。

实现代码

从小到大

#include<stdio.h>

int main()
{
	int numbers[10],t;
	printf("input 10 numbers:\n");
	for(int i=0;i<10;i++){
		scanf("%d",&numbers[i]);
	}
	for(int j=0;j<10;j++){
		for(int k=0;k<10;k++){
			if(numbers[j]<numbers[k]){
				t = numbers[j];
				numbers[j] = numbers[k];
				numbers[k] = t;
			}
		}
	}
	for(int i=0;i<10;i++){
		printf(" %d ",numbers[i]);
	}
	return 0;
}

从大到小

#include<stdio.h>

int main()
{
	int numbers[10],t;
	printf("input 10 numbers:\n");
	for(int i=0;i<10;i++){
		scanf("%d",&numbers[i]);
	}
	for(int j=0;j<10;j++){
		for(int k=0;k<10;k++){
			if(numbers[j]>numbers[k]){
				t = numbers[j];
				numbers[j] = numbers[k];
				numbers[k] = t;
			}
		}
	}
	for(int i=0;i<10;i++){
		printf(" %d ",numbers[i]);
	}
	return 0;
}

快速排序(Quick Sort)

主要思想

快速排序法是这五个排序方法中性能最好的算法，快速排序运用了分治思想和递归函数，所以快速排序也是这五个排序中最难的一个。

快速排序中要先找到一个目标值(target)，然后将小于目标值的数放到嘴边，将大于目标值的数放到右边，然后重复以上操作，直到每个元素单独成为一部分。

实现代码

从小到大

# include <stdio.h>
void quickSort(int *number, int first, int last);

int main(){
	int numbers[10];
	printf("input 10 numbers:\n");
	for(int i=0;i<10;i++){
		scanf("%d",&numbers[i]);
	}
	quickSort(numbers,0,9);
	for(int j=0;j<10;j++){
		printf("  %d  ",numbers[j]);
	}
	return 0;
}

void quickSort(int *number, int first, int last) {
	int i, j, pivot;
	int temp;
	if (first<last) {
		pivot = first;
		i = first;
		j = last;
		while (i<j) {
			while (number[i] <= number[pivot] && i<last)
				i++;
			while (number[j]>number[pivot])
				j--;
			if (i<j) {
				temp = number[i];
				number[i] = number[j];
				number[j] = temp;
			}
		}
		temp = number[pivot];
		number[pivot] = number[j];
		number[j] = temp;
		quickSort(number, first, j - 1);
		quickSort(number, j + 1, last);
	}
}

从大到小

# include <stdio.h>
void quickSort(int *number, int first, int last);

int main(){
	int numbers[10];
	printf("input 10 numbers:\n");
	for(int i=0;i<10;i++){
		scanf("%d",&numbers[i]);
	}
	quickSort(numbers,0,9);
	for(int j=0;j<10;j++){
		printf("  %d  ",numbers[j]);
	}
	return 0;
}

void quickSort(int *number, int first, int last) {
	int i, j, pivot;
	int temp;
	if (first<last) {
		pivot = first;
		i = first;
		j = last;
		while (i<j) {
			while (number[i] >= number[pivot] && i<last)
				i++;
			while (number[j]<number[pivot])
				j--;
			if (i<j) {
				temp = number[i];
				number[i] = number[j];
				number[j] = temp;
			}
		}
		temp = number[pivot];
		number[pivot] = number[j];
		number[j] = temp;
		quickSort(number, first, j - 1);
		quickSort(number, j + 1, last);
	}
}

简单选择排序(Simple Selection Sort)

主要思想

设一组元素有n个元素，选择这n个元素中最小的一个与第一个元素交换位置，再在剩下的n-1个元素中选择最小的一个与第二个元素交换位置，直到在最后两个元素中选择最小的一个放在倒数第二的位置上，排序完成。

实现代码

从小到大

#include<stdio.h>

int main()
{
	int a[10],i,j,t;
	printf("input 10 numbers:\n");
	for(i=0;i<10;i++){
		scanf("%d",&a[i]);
	}
	for(i=0;i<10;i++)
	{
		t=i;
		for(j=i+1;j<10;j++){
			if(a[t]>a[j])
			{
				t=j;
			}
		}
		int temp = a[i];
		a[i]=a[t];
		a[t]=temp;
	}
	for(i=0;i<10;i++){
		printf("%d",a[i]);
	}
  return 0;
}

从大到小

#include<stdio.h>

int main()
{
	int a[10],i,j,t;
	printf("input 10 numbers:\n");
	for(i=0;i<10;i++){
		scanf("%d",&a[i]);
	}
	for(i=0;i<10;i++)
	{
		t=i;
		for(j=i+1;j<10;j++){
			if(a[t]<a[j])
			{
				t=j;
			}
		}
		int temp = a[i];
		a[i]=a[t];
		a[t]=temp;
	}
	for(i=0;i<10;i++){
		printf("%d",a[i]);
	}
  return 0;
}