1.最基础的排序算法
思想：每次使用交换的方式将剩余元素中较大的元素放到一端，直到剩余元素为0的时候排序结束。
#include<stdio.h>
int main() {
int a[5] = {1, 3, 5, 10, 7};
printf("排序前：");
for (int i = 0; i < 5; i++)
printf("%d ", a[i]);
int temp = 0;
//每次循环将最大值交换到数组最右端
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5 - i; j++) {
//每遍历一次数组，可以确定当前剩余元素中的最大值
if (a[j] > a[j + 1]) {
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
printf("\n排序后：");
for (int i = 0; i < 5; i++)
printf("%d ", a[i]);
}
排序结果：
有序列[0,i-1]，无序列[i,n]，从无序列中选择最小（大）的元素与a[i]交换
#include <stdio.h>
void selectSort(int *a) {
for (int i = 0; i < 10; i++) {
int k = i; //记录最小值下标
for (int j = i; j < 10; j++) {
if (a[j] < a[k]) {
k = j; //重新记录最小值下标
}
}
int temp = a[i];
a[i] = a[k];
a[k] = temp;
}
}
int main() {
int A[10] = {22, 4, 7, 1, 8, 0, 14, 6, 5, 2};
printf("排序前: ");
for (int i = 0; i < 10; i++) {
printf("%d ", A[i]);
}
printf("\n排序后: ");
selectSort(A);
for (int i = 0; i < 10; i++) {
printf("%d ", A[i]);
}
}
排序结果：
思想：假设第一个元素已经有序 从第二个元素开始在有序列中寻找合适位置插入
#include <stdio.h>
void insertSort(int *a) {
//假设第一个元素已经有序 从第二个元素开始在有序列中寻找合适位置
for (int i = 1; i < 10; i++) {
int temp = a[i]; //记录待插入元素
int j = i;//[0,i-1] 为有序列
while (j > 0 && temp < a[j - 1]) {//待插入元素小于有序对最后一个元素才进行排序
a[j] = a[j - 1];//给待插入元素空出位置
j--;
}
a[j] = temp;
}
}
int main() {
int A[10] = {22, 4, 7, 1, 8, 0, 14, 6, 5, 2};
printf("排序前: ");
for (int i = 0; i < 10; i++) {
printf("%d ", A[i]);
}
printf("\n排序后: ");
insertSort(A);
for (int i = 0; i < 10; i++) {
printf("%d ", A[i]);
}
}
排序结果：
加上头文件#include “algorithm”
using namespace std;
sort(首元素地址，尾元素地址的下一个地址，比较函数(非必填));——如果不填写比较函数默认递增排序
#include <stdio.h>
#include "algorithm"
using namespace std;
int main() {
int a[10] = {22, 4, 7, 1, 8, 0, 14, 6, 5, 2};
printf("排序前: \n");
for (int i = 0; i < 10; i++) {
printf("%d ", a[i]);
}
printf("\n将a0到a3排序后: \n");
sort(a, a + 3 + 1);//尾元素的下一地址
for (int i = 0; i < 10; i++) {
printf("%d ", a[i]);
}
printf("\n将a0到a9从小到大排序后: \n");
sort(a, a + 9 + 1);
for (int i = 0; i < 10; i++) {
printf("%d ", a[i]);
}
}
排序结果：
#include <stdio.h>
#include "algorithm"
using namespace std;
bool cmp(int a, int b) {
return a > b;//左大右小 递减
// return a<b;//左小右大 递增
}
int main() {
int a[10] = {22, 4, 7, 1, 8, 0, 14, 6, 5, 2};
printf("排序前: \n");
for (int i = 0; i < 10; i++) {
printf("%d ", a[i]);
}
printf("\n将a0到a3排序后: \n");
sort(a, a + 3 + 1, cmp);//尾元素的下一地址
for (int i = 0; i < 10; i++) {
printf("%d ", a[i]);
}
printf("\n将a0到a9从小到大排序后: \n");
sort(a, a + 9 + 1, cmp);
for (int i = 0; i < 10; i++) {
printf("%d ", a[i]);
}
}
排序结果：
#include <stdio.h>
#include "algorithm"
using namespace std;
struct node {
int x, y;
} ssd[10];
bool cmp(node a, node b) {
return a.x > b.x;//左大右小 按x的值递减排序
}
bool cmp2(node a, node b) {
//如果 x相同 按照y从小打到排序
if (a.x == b.x)
return a.y < b.y;
else
return a.x > b.x;
}
int main() {
ssd[0].x = 2;//{2,2}
ssd[0].y = 2;
ssd[1].x = 1;//{1,3}
ssd[1].y = 3;
ssd[2].x = 2;//{2,1}
ssd[3].y = 1;
printf("排序前: \n");
for (int i = 0; i < 3; i++) {
printf("{%d,%d} ", ssd[i].x, ssd[i].y);
}
printf("\n将ssd0到ssd3 按x递减排序后: \n");
sort(ssd, ssd + 2 + 1, cmp);//递减排序
for (int i = 0; i < 3; i++) {
printf("{%d,%d} ", ssd[i].x, ssd[i].y);
}
printf("\n将ssd0到ssd3 如果 x相同 按照y从小打到排序后: \n");
sort(ssd, ssd + 2 + 1, cmp2);//递减排序
for (int i = 0; i < 3; i++) {
printf("{%d,%d} ", ssd[i].x, ssd[i].y);
}
}
排序结果：
目的：使得A[0]左侧元素不超过A[0]，右侧元素都大于A[0]
思路：1.只要A[R]大于A[0],就把R不断左移，直到A[R]小于A[0]时停止左移，将A[L]与A[R]交换
2.只要A[L]小于A[0],就把L不断右移，直到A[L]大于A[0]时停止右移，将A[L]与A[R]交换 重复1,2直到L=R
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <cmath>
#include <unordered_set>
//对区间[Left,Right]划分 选取最左侧元素为主元
int Partition(int A[], int left, int right) {
int temp = A[left];
while (left < right) {
while (right > left && A[right] > temp) {
right--;
}
A[left] = A[right];
while (right > left && A[left] < temp) {
left++;
}
A[right] = A[left];
}
A[left] = temp;//把temp 放到 left=right 的地方
return left;//返回相遇坐标
}
//选取最左侧主元，最坏情况下时间按复杂度 O(n^2)降低时间复杂度 选取随机主元快速排序
int randPartition(int A[], int left, int right) {
//生成[left,right]之间随机数
int p = round(1.0 * rand() / RAND_MAX * (right - left) + left);
//交换第一个元素和A[p]
int temp1 = A[p];
A[p] = A[left];
A[left] = temp1;
int temp = A[left];
while (left < right) {
while (right > left && A[right] > temp) {
right--;
}
A[left] = A[right];
while (right > left && A[left] < temp) {
left++;
}
A[right] = A[left];
}
A[left] = temp;//把temp 放到 left=right 的地方
return left;//返回相遇坐标
}
//快速排序 left,right 初值为序列首位下标
void quickSort(int A[], int left, int right) {
if (left < right) {
//将区间一分为二
int pos = Partition(A, left, right);
//对左右区间分别进行排序
quickSort(A, left, pos - 1);
quickSort(A, pos + 1, right);
}
}
int main() {
int A[10];
//生成随机序列
srand(time(NULL));
//生成指定范围随机数 rand()%(b-a+1)+a
//超出范围32767 的随机数 (round)(1.0*rand()/RAND_MAX*(b-a)+a)
printf("生成随机序列\n");
for (int i = 0; i < 10; i++) {
//生成[0,100] 范围的随机数
A[i] = rand() % (100 - 0 + 1) + 0;
printf("%d ", A[i]);
}
printf("\n选择最左侧主元进行快速排序后\n");
//选择最左侧主元进行快速排序
Partition(A, 0, 9);
for (int i = 0; i < 10; i++) {
printf("%d ", A[i]);
}
printf("\n选择随机主元进行快速排序后\n");
randPartition(A, 0, 9);
for (int i = 0; i < 10; i++) {
printf("%d ", A[i]);
}
return 0;
}
测试结果：
