1. 冒泡排序
//基本思想：比较相邻的两个数，如果前者比后者大，则进行交换。每一轮排序结束，选出一个未排序中最大的数放到数组后面。
#include<stdio.h>
//冒泡排序算法
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;
}
}
}
int main() {
int arr[] = { 10,6,5,2,3,8,7,4,9,1 };
int n = sizeof(arr) / sizeof(int);
bubbleSort(arr, n);
printf("排序后的数组为：\n");
for (int j = 0; j<n; j++)
printf("%d ", arr[j]);
printf("\n");
return 0;
}
/**
gcc bubbleSort.c
time && ./a.out bubbleSort.c && time
shell 1.21s user 0.53s system 0% cpu 11:00.66 total
children 1.26s user 1.25s system 0% cpu 11:00.66 total
排序后的数组为：
1 2 3 4 5 6 7 8 9 10
shell 1.21s user 0.53s system 0% cpu 11:00.66 total
children 1.27s user 1.25s system 0% cpu 11:00.66 total
0.01s左右
*/
1.1 冒泡升级版
#include<stdio.h>
//升级版冒泡排序算法
void bubbleSort_1(int *arr, int n) {
//设置数组左右边界
int left = 0, right = n - 1;
//当左右边界未重合时，进行排序
while (left < right) {
//从左到右遍历选出最大的数放到数组右边
for (int i =left; i < right; i++)
{
if (arr[i] > arr[i + 1])
{
int temp = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = temp;
}
}
right--;
//从右到左遍历选出最小的数放到数组左边
for (int j = right;j >= left; j--)
{
if (arr[j + 1] < arr[j])
{
int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp;
}
}
left++;
}
}
int main() {
int arr[] = { 10,6,5,2,3,8,7,4,9,1 };
int n = sizeof(arr) / sizeof(int);
bubbleSort_1(arr, n);
printf("排序后的数组为：\n");
for (int j = 0; j<n; j++)
printf("%d ", arr[j]);
printf("\n");
return 0;
}
2. 堆排序
#include<stdio.h>
// 创建大堆顶，i为当节点，n为堆的大小
// 从第一个非叶子结点i从下至上，从右至左调整结构
// 从两个儿子节点中选出较大的来与父亲节点进行比较
// 如果儿子节点比父亲节点大，则进行交换
void CreatHeap(int a[], int i, int n) {
// 注意数组是从0开始计数，所以左节点为2*i+1，右节点为2*i+2
for (; i >= 0; --i)
{
int left = i * 2 + 1; //左子树节点
int right = i * 2 + 2; //右子树节点
int j = 0;
//选出左右子节点中最大的
if (right < n) {
j= a[left] > a[right]?left:right;
}
else
j = left;
//交换子节点与父节点
if (a[j] > a[i]) {
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
}
}
// 进行堆排序，依次选出最大值放到最后面
void HeapSort(int a[], int n) {
//初始化构造堆
CreatHeap(a, n/2-1, n);
//交换第一个元素和最后一个元素后，堆的大小减1
for (int j = n-1; j >= 0; j--) {
//最后一个元素和第一个元素进行交换
int tmp = a[0];
a[0] = a[j];
a[j] = tmp;
int i = j / 2 - 1;
CreatHeap(a, i, j);
}
}
int main() {
int a[] = { 10,6,5,7,12,8,1,3,11,4,2,9,16,13,15,14 };
int n = sizeof(a) / sizeof(int);
HeapSort(a, n);
printf("排序好的数组为：");
for (int l = 0; l < n; l++) {
printf("%d ", a[l]);
}
printf("\n");
return 0;
}
3. 插入排序
#include<stdio.h>
void InsertSort(int *a, int n) {
int tmp = 0;
for (int i = 1; i < n; i++) {//从第二个开始 也就是后一个
int j = i - 1; // 第一个也就是前一个
if (a[i] < a[j]) { // 前面一个大于后面一个 就要交换位置
tmp = a[i]; //后面那个暂存
a[i] = a[j]; //前面的那个 替换给 后面的那个
while (tmp < a[j-1]) { //
a[j] = a[j-1];
j--;
}
a[j] = tmp;
}
}
}
int main() {
int a[] = { 11,7,9,22,10,18,4,43,5,1,32};
int n = sizeof(a)/sizeof(int);
InsertSort(a, n);
printf("排序好的数组为：");
for (int i = 0; i < n; i++) {
printf(" %d", a[i]);
}
printf("\n");
return 0;
}
4. 合并排序
#include <stdio.h>
#include <limits.h>
#include <stdlib.h>
// 合并两个已排好序的数组
void Merge(int a[], int left, int mid, int right)
{
int len = right - left + 1; // 数组的长度
int *temp = (int*)malloc(sizeof(int)*len); // 分配个临时int数组
int k = 0;
int i = left; // 前一数组的起始元素
int j = mid + 1; // 后一数组的起始元素
while (i <= mid && j <= right)
{
// 选择较小的存入临时数组
temp[k++] = a[i] <= a[j] ? a[i++] : a[j++];
}
while (i <= mid)
{
temp[k++] = a[i++];
}
while (j <= right)
{
temp[k++] = a[j++];
}
for (int k = 0; k < len; k++)
{
a[left++] = temp[k];
}
}
// 递归实现的归并排序
void MergeSort(int a[], int left, int right)
{
if (left == right)
return;
int mid = (left + right) / 2;
MergeSort(a, left, mid);
MergeSort(a, mid + 1, right);
Merge(a, left, mid, right);
}
int main() {
int a[] = { 5,1,9,2,8,7,10,3,4,0,6 };
int n = sizeof(a) / sizeof(int);
MergeSort(a, 0, n - 1);
printf("排序好的数组为：");
for (int k = 0; k < n; ++k)
printf("%d ", a[k]);
printf("\n");
return 0;
}
5. 快速排序(快排)
#include<stdio.h>
void swap(int *x, int *y) {
int tmp = *x;
*x = *y;
*y = tmp;
}
//分治法把数组分成两份 分而治之
int patition(int *a, int left,int right) {
int j = left; //用来遍历数组
int i = j - 1; //用来指向小于基准元素的位置
int key = a[right]; //基准元素
//从左到右遍历数组，把小于等于基准元素的放到左边，大于基准元素的放到右边
for (; j < right; ++j) {
if (a[j] <= key)
swap(&a[j], &a[++i]);
}
//把基准元素放到中间
swap(&a[right], &a[++i]);
//返回数组中间位置
return i;
}
//快速排序
void quickSort(int *a,int left,int right) {
if (left>=right)
return;
int mid = patition(a,left,right);
quickSort(a, left, mid - 1);
quickSort(a, mid + 1, right);
}
int main() {
int a[] = { 10,6,5,7,12,8,1,3,11,4,2,9,16,13,15,14 };
int n = sizeof(a) / sizeof(int);
quickSort(a, 0,n-1);
printf("排序好的数组为：");
for (int l = 0; l < n; l++) {
printf("%d ", a[l]);
}
printf("\n");
return 0;
}
6. 选择排序
#include<stdio.h>
void SelectSort(int *a, int n) {
for (int i = 0; i < n; i++)
{
int key = i; // 临时变量用于存放数组最小值的位置
for (int j = i + 1; j < n; j++) {
if (a[j] < a[key]) {
key = j; // 记录数组最小值位置
}
}
if (key != i)
{
int tmp = a[key]; a[key] = a[i]; a[i] = tmp; // 交换最小值
}
}
}
int main() {
int a[] = { 12,4,15,2,6,22,8,10,1,33,45,24,7 };
int n = sizeof(a) / sizeof(int);
SelectSort(a, n);
printf("排序好的数组为： ");
for (int k = 0; k < n; k++)
printf("%d ", a[k]);
printf("\n");
return 0;
}
7. shell排序
#include<stdio.h>
// 进⾏行行插⼊入排序
// 初始时从dk开始增⻓长，每次⽐比较步⻓长为dk void Insrtsort(int *a, int n,int dk) {
for (int i = dk; i < n; ++i) {
int j = i - dk;
if (a[i] < a[j]) { //
int tmp = a[i];
⽐比较前后数字⼤大⼩小
a[i] = a[j];
while (a[j] > tmp) {
a[j+dk] = a[j];
j -= dk; }
a[j+dk] = tmp;
void ShellSort(int *a, int n) {
int dk = n / 2; //
while (dk >= 1) {
Insrtsort(a, n, dk);
dk /= 2; }
}
// //
//
作为临时存储 寻找tmp的插⼊入位置
插⼊入tmp
} }
}
int main() {
int a[] = { 5,12,35,42,11,2,9,41,26,18,4 }; int n = sizeof(a) / sizeof(int); ShellSort(a, n);
printf("排序好的数组为:");
for (int j = 0; j < n; j++) {
printf("%d ", a [j]);
}
return 0;
}
