|
排序算法种类:
冒泡 选择 插入(希尔)
快速排序 分组排序 基数排序 桶排序 堆排序 归并排序?
#include <stdio.h>
void print(int* a, int len, bool isBefore = true);
int main() {
int arr[10] = { 1,9,66,0,33,5,2,88,666,233 };
print(arr, 10);
print(arr, 10, false);
while (1);
return 0;
}
void print(int* a, int len, bool isBefore) {
if (isBefore)
printf("before sort:");
else
printf("after sort:");
for (int i = 0; i < len; i++)
printf("%d", a[i]);
printf("\n");
}
中间填充排序算法
冒泡排序(最简单):
思想(升序):
比较相邻的两个元素哪个比较大,若大的在后面,不管,若小的在后面交换
一轮过后,第len个数据就是最大的,
#include <stdio.h>
void print(int* a, int len, bool isBefore = true);
void bubble_sort(int* a, int len);
int main() {
int arr[10] = { 1,9,66,0,33,5,2,88,666,233 };
print(arr, 10);
printf("bubble_sort\n");
bubble_sort(arr, 10);
print(arr, 10, false);
while (1);
return 0;
}
//冒泡排序
void bubble_sort(int* a, int len)
{
int temp;
for (int i = 0; i < len; i++) {//外层循环
for (int j = 0; j < len - i - 1; j++) {
printf("i:%d,j:%d", i, j);
if (a[j] > a[j + 1]) {
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
}
void print(int* a, int len, bool isBefore) {
if (isBefore)
printf("before sort:");
else
printf("after sort:");
for (int i = 0; i < len; i++)
printf("%d", a[i]);
printf("\n");
}
选择排序:从待排数组中选择最合适的
一轮选一个最小的,下一轮继续选个最小的,9轮之后即可
#include <stdio.h>
void select_sort(int* a, int len);
void print(int* a, int len, bool isBefore = true);
int main() {
int arr[10] = { 1,9,66,0,33,5,2,88,666,233 };
void select_sort(arr, 10);
print(arr, 10, false);
while (1);
return 0;
}
void select_sort(int* a, int len) {
int temp;
int minidx;
for (int i = 0; i < len - 1; i++) {
temp = a[i];
minidx = i;
for (int j = i; j < len; j++) {
minidx = (a[j] < a[minidx]) ? j : minidx;
}
a[i] = a[minidx];
a[minidx] = temp;
}
}
void print(int* a, int len, bool isBefore) {
if (isBefore)
printf("before sort:");
else
printf("after sort:");
for (int i = 0; i < len; i++)
printf("%d", a[i]);
printf("\n");
}
插入排序
先假设数组有序,每次往有序数组中插入一个
#include <stdio.h>
#include <algorithm>
void print(int* a, int len, bool isBefore = true);
void insert_sort(int* a, int len);
int main() {
int arr[10] = { 1,9,66,0,33,5,2,88,666,233 };
printf("insert_sort\n");
insert_sort(arr, 10);
print(arr, 10, false);
while (1);
return 0;
}
void insert_sort(int* a, int len) {
int temp;
int j;
for (int i = 1; i < len; i++) {
temp = a[i];
j = i - 1;
while (j >= 0 && a[j] > temp) {
a[j + 1] = a[j];
j--;
}
a[j + 1] = temp;
print(a, 10);
}
}
void print(int* a, int len, bool isBefore) {
if (isBefore)
printf("before sort:");
else
printf("after sort:");
for (int i = 0; i < len; i++)
printf("%d", a[i]);
printf("\n");
}
希尔排序(对插入排序时间复杂度的优化)
引入步长概念,每次按照步长分组,组内做插入排序
步长每次变化,通常折半
#include <stdio.h>
void print(int* a, int len, bool isBefore = true);
void shell_sort(int* a, int len);
int main() {
int arr[10] = { 1,9,66,0,33,5,2,88,666,233 };
shell_sort(arr, 10);
print(arr, 10, false);
while (1);
return 0;
}
void shell_sort(int* a, int len) {
int step = len / 2;
int temp = 0;
int j;
while (step) {
for (int i = temp; i < len; i++) {
temp = a[i];
j = i - step;
while (j >= 0 && a[j] > temp) {
a[j + 1] = a[j];
j--;
}
a[j + step] = temp;
print(a, 10);
}
step = step / 2;
}
}
void print(int* a, int len, bool isBefore) {
if (isBefore)
printf("before sort:");
else
printf("after sort:");
for (int i = 0; i < len; i++)
printf("%d", a[i]);
printf("\n");
}
|