冒泡排序
#include<stdio.h>
void exchange(int* a,int* b){
int c = *a;
*a = *b;
*b = c;
}
void gulugulu(int* arr,int n) {
for (int i = 1; i < n; i++) {
int flag = 0;
for (int j = 0; j < n-i;j++) {
if (arr[j] > arr[j + 1]) {
exchange(&arr[j], &arr[j + 1]);
flag = 1;
}
}
if (flag == 0) {
return 0;
}
}
}
int main() {
int arr[] = {1,8,3,2,6,9,4};
int n = sizeof(arr) / sizeof(int);
gulugulu(arr,n);
for (int i = 0; i < n;i++) {
printf("%d ",arr[i]);
}
}
O(n²)
稳定
选择排序
#include<stdio.h>
void exchange(int* a,int* b){
int c = *a;
*a = *b;
*b = c;
}
void xuanzhe(int* arr,int n) {
for (int i = 1; i < n; i++) {
int index = 0;
int j;
for (j = 0; j <= n - i; j++) {
if (arr[j] > arr[index]) {
index = j;
}
}
exchange(&arr[index], &arr[j-1]);
}
}
int main() {
int arr[] = {1,8,3,2,6,9,4};
int n = sizeof(arr) / sizeof(int);
xuanzhe(arr,n);
for (int i = 0; i < n;i++) {
printf("%d ",arr[i]);
}
}
O(n²)
不稳定
插入排序
#include<stdio.h>
void insertsort(int* arr,int n) {
int i;
int j;
for (i = 1; i < n; i++) {
int a = arr[i];
for (j = i - 1; j >= 0 && arr[j] > a; j--) {
arr[j + 1] = arr[j];
}
arr[j + 1] = a;
}
}
int main() {
int arr[] = { 4,5,6,5,8,9 };
int n = sizeof(arr) / sizeof(int);
insertsort(arr, n);
for (int i = 0; i < n;i++) {
printf("%d ",arr[i]);
}
}
O(n²)
稳定
计数排序
#include<stdio.h>
int maxval(int* three,int n){
int max = three[0];
for (int i = 0; i < n; i++) {
if (three[i] > max) {
max = three[i];
}
}
return max;
}
void bucketsort(int* three, int n) {
int max = maxval(three,n );
int* bucket = (int*)malloc(sizeof(int)*(max + 1));
for (int i = 0; i <= max; i++) {
bucket[i] = 0;
}
for (int i = 0;i<n; i++) {
bucket[three[i]]++;
}
int index = 0;
for (int i = 0; i <= max;i++) {
while (bucket[i]>0) {
three[index++] = i;
bucket[i]--;
}
}
}
int main() {
int three[] = {8,2,3,4,6,5,3,8,1};
int n = sizeof(three) / sizeof(int);
bucketsort(three, n);
for (int i = 0; i < n;i++) {
printf("%d ",three[i]);
}
return 0;
}
O(n)
稳定
堆排序
#include<stdio.h>
void exchange(int* a, int* b) {
int c = *a;
*a = *b;
*b = c;
}
void adjust(int* arr,int start,int end) {
int father = start;
int child = father * 2 + 1;
while (child <= end) {
if (child + 1 <= end && arr[child] < arr[child + 1]) {
child++;
}
if (arr[child] > arr[father]) {
exchange(&arr[child],&arr[father]);
father = child;
child = father * 2 + 1;
}
else {
break;
}
}
}
void heapsort(int* arr,int n) {
for (int i = n / 2 - 1; i >= 0; i--) {
adjust(arr,i,n-1);
}
for (int j = n - 1; j >= 0;j--) {
exchange(&arr[0],&arr[j]);
adjust(arr,0,j-1);
}
}
int main() {
int arr[] = { 4,5,6,5,8,9 };
int n = sizeof(arr) / sizeof(int);
heapsort(arr, n);
for (int i = 0; i < n;i++) {
printf("%d ",arr[i]);
}
return 0;
}
O(nlogn)
不稳定
快速排序
#include<stdio.h>
void exchange(int* a, int* b) {
int c = *a;
*a = *b;
*b = c;
}
void paixu(int* arr,int a,int b) {
if (a >= b) {
return;
}
int index = a;
int i = a - 1 ;
int j = b + 1;
int temp = arr[index];
while (index<j) {
if (arr[index]==temp) {
index++;
}
else if(arr[index]<temp){
exchange(&arr[++i],&arr[index]);
index++;
}
else if (arr[index]>temp) {
exchange(&arr[--j],&arr[index]);
}
}
paixu(arr,a,i);
paixu(arr,j,b);
}
int main() {
int arr[] = { 1,458,289,14,57,2,63,14,78,6 };
int n = sizeof(arr) / sizeof(int);
int i = 0;
paixu(arr,i, n-1);
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}
O(nlogn)
不稳定
归并排序
#include<stdio.h>
#include<stdlib.h>
void merg(int* arr, int l, int mid, int r) {
int* temp = (int*)malloc(sizeof(int) * (r - l + 1));
int i = l;
int j = mid+1;
int index = 0;
while (i<=mid&&j<=r) {
if (arr[i] <= arr[j]) {
temp[index++] = arr[i++];
}
else {
temp[index++] = arr[j++];
}
}
while (j <= r) {
temp[index++] = arr[j++];
}
while (i <= mid) {
temp[index++] = arr[i++];
}
i = l;
for (index = 0; index < r - l + 1; index++) {
arr[i++] = temp[index];
}
free(temp);
}
void mergsort(int* arr,int l,int r) {
if (l >= r) {
return;
}
int mid = (l + r) / 2;
mergsort(arr,l,mid);
mergsort(arr,mid+1,r);
merg(arr,l,mid,r);
}
int main() {
int arr[] = { 1,458,289,14,57,2,63,14,78,6 };
int n = sizeof(arr) / sizeof(int);
int i = 0;
mergsort(arr, i, n - 1);
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}
O(nlogn)
稳定