选择、插入、冒泡、归并、快速排序 C/C++
2021-09-03 本文已影响0人
HardMan
// sort.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#include <iostream>
void switchnums (int& a, int& b) {
int temp = a;
a = b;
b = temp;
}
/*--------------归并排序----------------*/
void sort_(int* nums, int left, int right) {
int size = right - left + 1;
int* temp = new int[size];
for (int i = 0;i < size;i++) {
temp[i] = nums[left + i];
}
int tempmid = (size - 1) / 2;
int templeft = 0;
int tempright = tempmid + 1;
for (int k = 0;k < size;k++) {
if (templeft > tempmid) {
nums[left + k] = temp[tempright];
tempright++;
continue;
}
if (tempright > size - 1) {
nums[left + k] = temp[templeft];
templeft++;
continue;
}
if (temp[templeft] < temp[tempright]) {
nums[left + k] = temp[templeft];
templeft++;
}
else {
nums[left + k] = temp[tempright];
tempright++;
}
}
delete[] temp;
}
void mergesort(int* nums, int left, int right) {
if (left >= right) {
return;
}
int mid = left + (right - left) / 2;
mergesort(nums, left, mid);
mergesort(nums, mid + 1, right);
sort_(nums, left, right);
}
void divedandcpsort(int* nums, int length) {
mergesort(nums, 0, length - 1);
}
/*---------------------归并排序 end--------------------------------*/
归并排序思想：
将一个数组分成两半，每一半数组进行归并排序后，再对两半数组进行一次合并。利用
image.png
/*---------------------快速排序 start--------------------------------*/
int partsort(int arr[], int left, int right) {
int compareValue = arr[left];
int v = left;//小于目标值的区域最右位置初始化为left
for (int i = left+1;i <=right;i++){
if (arr[i] < compareValue) {
v++;//小于目标值的区域扩大1
switchnums(arr[v], arr[i]);
}
}
switchnums(arr[v], arr[left]);
return v;
}
void quick_sort(int arr[], int left, int right) {
if (left >= right) {
return;
}
int p = partsort(arr, left, right);
quick_sort(arr,left, p - 1);
quick_sort(arr, p + 1, right);
}
void quickSort(int arr[], int length) {
quick_sort(arr, 0, length - 1);
}
/*---------------------快速排序 end--------------------*/
快速排序的思想:
image.png
/*---------------插入排序 start-----------------*/
void insertSort(int arr[], int length) {
for (int i = 1;i < length;i++) {
for (int j = i;j - 1 > 0;j--) {
if (arr[j] < arr[j - 1]) {
switchnums(arr[j], arr[j - 1]);
}
}
}
}
/*-----------------插入排序 end------------------------*/
插入排序的思想:
插入排序类似于打扑克，抽到一张牌后，插入到手中已拍好序的牌
insert.gif
/*------------------选择排序 start----------------------*/
void chooseSort(int arr[], int length) {
for (int i = 0;i < length;i++) {
int min = i;
for (int j = i + 1;j < length;j++) {
if (arr[j] < arr[min]) {
min = j;
}
}
switchnums(arr[i], arr[min]);
}
}
/*--------------------选择排序 end------------------------*/
选择排序的思想：在一次循环中，找到最小的值的位置p，将p与i进行替换。i从0开始，每次循环都会递增，直到末尾。
choose.gif
/*------------------- 冒泡排序 start------------------------*/
void bubblesort(int arr[],int length) {
for (int i = 0;i < length;i++) {
for (int j = i; j + 1 < length;j++) {
if (arr[j + 1] < arr[j]) {
switchnums(arr[j], arr[j + 1]);
}
}
}
}
/*------------------冒泡排序 end----------------------------*/
冒泡排序的思想：
就跟气泡一样，大的气泡往下层，小的气泡往上浮。即每次循环，都将最大的数挪到末尾。
比较相邻的元素，如果第一个比第二个大，则交换。再比较第二个和第三个，直到末尾。
bubble.gif
void printNums(int arr[],int length) {
for (int i = 0;i < length;i++) {
std::cout << arr[i] << std::endl;
}
}
int main()
{
int nums[] = { 1,5,2,51,33,15,132,51,3,6 };
int length = sizeof(nums) / sizeof(int);
std::cout << "选择排序" << std::endl;
chooseSort(nums, length);
printNums(nums, length);
int nums1[] = { 1,5,2,51,33,15,132,51,3,6 };
std::cout << "冒泡排序" << std::endl;
bubblesort(nums1, length);
printNums(nums1, length);
int nums2[] = { 1,5,2,51,33,15,132,51,3,6 };
std::cout << "插入排序" << std::endl;
insertSort(nums2, length);
printNums(nums2, length);
int nums3[] = { 1,5,2,51,33,15,132,51,3,6 };
std::cout << "归并排序" << std::endl;
divedandcpsort(nums3, length);
printNums(nums3, length);
int nums4[] = { 1,5,2,51,33,15,132,51,3,6 };
std::cout << "快速排序" << std::endl;
quickSort(nums4, length);
printNums(nums4, length);
getchar();
}
```
