目录
不同测试点数据范围
一、冒泡排序
代码实现
#include<iostream>
using namespace std;
void swap(int &a, int &b) { int t = a; a = b; b = t; }
void Bubble_Sort(int *arr,int n)
{
for (int i = n - 1; i > 0; i--)
for (int j = 0; j < i; j++)
if (arr[j] > arr[j + 1]) swap(arr[j], arr[j + 1]);
}
int main()
{
int n;
cin>>n;
int* arr=new int[n];
for(int i=0;i<n;i++) cin>>arr[i];
Bubble_Sort(arr,n);
for(int i=0;i<n;i++) {if(i)cout<<' ';cout<<arr[i];}
return 0;
}
测试结果
二、选择排序
代码实现
#include<iostream>
using namespace std;
void Select_Sort(int *arr, int n)
{
for (int i = 0; i < n - 1; i++)
{
int pos = i;
for (int j = i + 1; j < n; j++)
if (arr[j] < arr[pos]) pos = j;
swap(arr[i], arr[pos]);
}
}
int main()
{
int n;
cin>>n;
int* arr=new int[n];
for(int i=0;i<n;i++) cin>>arr[i];
Select_Sort(arr,n);
for(int i=0;i<n;i++) {if(i)cout<<' ';cout<<arr[i];}
return 0;
}
测试结果
三、插入排序
代码实现
1. 数组实现
#include<iostream>
using namespace std;
void swap(int &a, int &b) { int t = a; a = b; b = t; }
void Insert_Sort_Array(int *arr, int n)
{
for (int i = 1; i < n; i++)
{
if (arr[i] > arr[i - 1]) continue;
else {
int tmp = arr[i], pos;
for (pos = i; pos > 0 && arr[pos - 1] > tmp; pos--) arr[pos] = arr[pos - 1];
arr[pos] = tmp;
}
}
}
int main()
{
int n;
cin>>n;
int* arr=new int[n];
for(int i=0;i<n;i++) cin>>arr[i];
Insert_Sort_Array(arr,n);
for(int i=0;i<n;i++) {if(i)cout<<' ';cout<<arr[i];}
return 0;
}
2. 链表实现
#include<iostream>
using namespace std;
void swap(int &a, int &b) { int t = a; a = b; b = t; }
struct number
{
int data; number*next;
number(int n) :data(n) { next = nullptr; }
};
void Insert_Sort_List(int *arr, int n)
{
if (n == 0 || n == 1) return;
number*head, *tail = head = new number(arr[0]), *tmp;
for (int i = 1; i < n; i++)
{
number*now = new number(arr[i]);
if (now->data >= tail->data) tail->next = now, tail = now;
else {
if (now->data <= head->data) now->next = head, head = now;
else {
tmp = head;
while (tmp->next->data < now->data) tmp = tmp->next;
now->next = tmp->next; tmp->next = now;
}
}
}tmp = head;
for (int i = 0; i < n; i++, tmp = tmp->next) arr[i] = tmp->data;
while (head) { tmp = head->next; delete head; head = tmp; }
}
int main()
{
int n;
cin>>n;
int* arr=new int[n];
for(int i=0;i<n;i++) cin>>arr[i];
Insert_Sort_List(arr,n);
for(int i=0;i<n;i++) {if(i)cout<<' ';cout<<arr[i];}
return 0;
}
测试结果
1. 数组测试结果
2. 链表测试结果
四、希尔排序（Hibbard增序）
代码实现
#include<iostream>
using namespace std;
void swap(int &a, int &b) { int t = a; a = b; b = t; }
void Shell_Sort(int *arr, int n)
{
for (int len = n & 1 ? n >> 1 : n + 1 >> 1; len > 0; len >>= 1)
{
for (int i = len; i < n; i++) {
int tmp = arr[i], j;
for (j = i; j >= len&&arr[j - len] > tmp; j -= len) arr[j] = arr[j - len];
arr[j] = tmp;
}
}
}
int main()
{
int n;
cin>>n;
int* arr=new int[n];
for(int i=0;i<n;i++) cin>>arr[i];
Shell_Sort(arr,n);
for(int i=0;i<n;i++) {if(i)cout<<' ';cout<<arr[i];}
return 0;
}
测试结果
五、归并排序
代码实现
1.递归实现
#include<iostream>
using namespace std;
void swap(int &a, int &b) { int t = a; a = b; b = t; }
void merge(int*arr,int*tmp, int head,int mid, int tail)
{
int h = head, t = mid+1, i = head;
while (h <= mid && t <= tail) tmp[i++] = arr[h] < arr[t] ? arr[h++] : arr[t++];
while (h <= mid) tmp[i++] = arr[h++];
while (t <= tail) tmp[i++] = arr[t++];
for (i = head; i <= tail; i++) arr[i] = tmp[i];
}
void Merge_ArrayRank(int*arr,int*tmp,int head,int tail)
{
if (head >= tail) return;
int mid = head + (tail - head >> 1);
Merge_ArrayRank(arr, tmp, head, mid);
Merge_ArrayRank(arr, tmp, mid + 1, tail);
merge(arr, tmp, head, mid, tail);
}
void Merge_Sort_Recursion(int *arr, int n)
{
if (n == 0 || n == 1) return;
int*tmp = new int[n];
Merge_ArrayRank(arr, tmp, 0, n - 1);
delete[]tmp;
}
int main()
{
int n;
cin>>n;
int* arr=new int[n];
for(int i=0;i<n;i++) cin>>arr[i];
Merge_Sort_Recursion(arr,n);
for(int i=0;i<n;i++) {if(i)cout<<' ';cout<<arr[i];}
return 0;
}
2.迭代实现
void Merge(int*arr, int*tmp, int head, int mid, int tail)
{
int h = head, t = mid + 1, i = head;
while (h <= mid && t <= tail) tmp[i++] = arr[h] < arr[t] ? arr[h++] : arr[t++];
while (h <= mid) tmp[i++] = arr[h++];
while (t <= tail) tmp[i++] = arr[t++];
}
void Merge_Sort_Unrecursion(int*arr, int*tmp, int n, int length)
{
int i;
for (i = 0; i <= n - 2 * length; i += 2 * length)
Merge(arr, tmp, i, i + length - 1, i + 2 * length - 1);
if (i < n - length) Merge(arr, tmp, i, i + length - 1, n - 1);
else for (int j = i; j < n; j++) tmp[j] = arr[j];
}
void Merge_Sort_Unrecursion(int *arr, int n)
{
int length = 1;
int *tmp = new int[n];
while (length < n)
{
Merge_Sort_Unrecursion(arr, tmp, n, length);
length *= 2;
Merge_Sort_Unrecursion(tmp, arr, n, length);
length *= 2;
}
delete[]tmp;
}
测试结果
1.递归结果
2.迭代结果
六、堆排序
代码实现
#include<iostream>
using namespace std;
void HeapInsert(int*arr,int n)
{
while (arr[(n - 1) / 2] < arr[n]) swap(arr[(n - 1) / 2], arr[n]), n = n - 1 >> 1;
}
void Heapify(int*arr, int n)
{
int pos = 0;
while (2 * pos + 1 < n)
{
int largest = 2 * pos + 2 < n&&arr[2 * pos + 2] > arr[2 * pos + 1] ? 2 * pos + 2 : 2 * pos + 1;
largest=arr[largest] > arr[pos] ? largest : pos;
if (largest == pos) break;
else swap(arr[largest], arr[pos]), pos = largest;
}
}
void Heap_Sort(int*arr, int n)
{
if (n == 0 || n == 1) return;
for (int i = 0; i < n; i++)HeapInsert(arr, i);
while (n > 0)
{
swap(arr[0], arr[--n]);
Heapify(arr, n);
}
}
int main()
{
int n;
cin>>n;
int* arr=new int[n];
for(int i=0;i<n;i++) cin>>arr[i];
Heap_Sort(arr,n);
for(int i=0;i<n;i++) {if(i)cout<<' ';cout<<arr[i];}
return 0;
}
测试结果
七、快速排序
代码实现
1. 随机数取主元
#include<iostream>
using namespace std;
void swap(int &a, int &b) { int t = a; a = b; b = t; }
void Quick_SortR(int *arr, int head, int tail)
{
if (head >= tail) return;
int target = rand() % (tail - head + 1) + head;
target = arr[target];
int i, l = i = head, r = tail;
while (i <= r)
{
if (arr[i] < target) if (i != l) swap(arr[l++], arr[i++]); else i++, l++;
else if (arr[i] == target) i++;
else swap(arr[i], arr[r--]);
}
Quick_SortR(arr, head, l - 1);
Quick_SortR(arr, r + 1, tail);
}
void Quick_Sort_Rand(int *arr, int n)
{
if (n == 0 || n == 1) return;
Quick_SortR(arr, 0, n - 1);
}
int main()
{
int n;
cin>>n;
int* arr=new int[n];
for(int i=0;i<n;i++) cin>>arr[i];
Quick_Sort_Rand(arr,n);
for(int i=0;i<n;i++) {if(i)cout<<' ';cout<<arr[i];}
return 0;
}
2. 中位数取主元
#include<iostream>
using namespace std;
void swap(int &a, int &b) { int t = a; a = b; b = t; }
void Quick_SortM(int *arr, int head, int tail)
{
if (head >= tail) return;
int median = head + (tail - head >> 1), target;
if (arr[head] > arr[median])swap(arr[head], arr[median]);
if (arr[median] > arr[tail])swap(arr[tail], arr[median]);
target = arr[median];
swap(arr[median], arr[tail - 1]);
int i, l = i = head, r = tail;
while (i <= r)
{
if (arr[i] < target) swap(arr[l++], arr[i++]);
else if (arr[i] == target) i++;
else swap(arr[i], arr[r--]);
}
Quick_SortM(arr, head, l - 1);
Quick_SortM(arr, r + 1, tail);
}
void Quick_Sort_Median(int *arr, int n)
{
if (n == 0 || n == 1) return;
Quick_SortM(arr, 0, n - 1);
}
int main()
{
int n;
cin>>n;
int* arr=new int[n];
for(int i=0;i<n;i++) cin>>arr[i];
Quick_Sort_Median(arr,n);
for(int i=0;i<n;i++) {if(i)cout<<' ';cout<<arr[i];}
return 0;
}
测试结果
1. 随机数取主元结果
2. 中位数取主元结果
八、基数排序
代码实现
#include<iostream>
using namespace std;
int maxi;
void getCompareTimes()
{
for (int i = 0;; i++) if (maxi == 0) { maxi = i; break; }
else maxi /= 10;
}
int getDigit(int num, int pos)
{
//cout << num << ' ';
if (num == 0 || pos == 1) return num % 10;
else return getDigit(num / 10, pos - 1);
}
void Bucket_Sort(int *arr, int n)
{
if (n == 0 || n == 1) return;
getCompareTimes();
int*bucket = new int[n];
for (int i = 1; i <= maxi; i++)
{
int*tmp = new int[20](); tmp += 10; // 模拟一下负数数组
for (int j = 0; j < n; j++) tmp[getDigit(arr[j], i)]++;
for (int j = -9; j < 10; j++) tmp[j] += tmp[j - 1];
for (int j = n - 1; j >= 0; j--) {int d = getDigit(arr[j], i); bucket[tmp[d] - 1] = arr[j]; tmp[d]--;}
for (int j = 0; j < n; j++) arr[j] = bucket[j];
tmp -= 10;
delete[]tmp;
}
delete[]bucket;
}
int main()
{
int n;
cin>>n;
int* arr=new int[n];
for(int i=0;i<n;i++) {cin>>arr[i]; maxi = maxi > arr[i] ? maxi : arr[i]; }
Bucket_Sort(arr,n);
for(int i=0;i<n;i++) {if(i)cout<<' ';cout<<arr[i];}
return 0;
}
测试结果
版权声明：本文为m0_63494135原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。