|
1.冒泡排序
????????通过重复地访问要排序的元素列，依次比较两个相邻的 元素 ，如果顺序（如从大到小、首字母从Z到A）与所需排序的顺序相反，就将两个元素交换，并使最大的元素移至最后一位，然后通过第二次排序使次大的元素移至倒数第二位，以此类推，直至所有元素有序
#include <iostream>
void swap(int &a, int &b) {
int temp = a;
a = b;
b = temp;
}
void Bubble_Sort(int list[], int n)
{
for (int i = 0; i < n - 1; i++)
{
for (int j = 0; j < n - i - 1; j++)
{
if (list[j] > list[j + 1])
{
swap(list[j], list[j + 1]);
}
}
}
}
int mian()
{
int list[12] = { 1,2,3,5,8,94,6,11,54,0,23,5 };
int n = 12;
Bubble_Sort(list, n);
//cout << sizeof(list) / sizeof(list[0]) << endl;
for (int i = 0;i < n; i++)
{
std::cout << list[i] << std::endl;
}
return 0;
}
2.插入排序
????????初始状态下，将待排序序列中的第一个元素看作是有序的子序列。从第二个元素开始，在不破坏子序列有序的前提下，将后续的每个元素插入到子序列中的适当位置。????????
void insert(int list[], int n) {
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (list[i] > list[j]) {
swap(list[i], list[j]);
}
}
}
}
3.计数排序
????????1. 找出待排序的数组中最大和最小的元素
????????2. 统计数组中每个值为i的元素出现的次数，存入数组C的第i项
????????3. 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
????????4. 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1
void count(int list[], int num) {
int max = 0, index = 0;
for (int i = 0; i < num; i++) {
if (max < list[i]) {
max = list[i];
}
}
int* cou = new int[max + 1]; //生成的是数组，delete需要加[]
for (int i = 0; i < max + 1; i++) {
cou[i] = 0; //计数数组赋初值
}
for (int i = 0; i < num; i++) {
cou[list[i]]++; //计数
}
for (int i = 0; i < max + 1; i++) {
int in = i;
while (cou[i] != 0) {
list[index] = in;
index++;
cou[i]--;
}
}
delete[] cou;
}
4.选择排序
????????1. 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
????????2. 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
????????3. 重复第二步，直到所有元素均排序完毕。
void select(int list[], int num) {
for (int i = 0; i < num-1; i++) {
int index = i;
for (int j = i + 1; j < num; j++) {
if (list[index] > list[j]) {
index = j;
}
}
swap(list[index], list[i]);
}
}
5.归并排序
????????算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。归并排序思路简单，速度仅次于快速排序，为稳定排序算法，一般用于对总体无序，但是各子项相对有序的数列。
void divide_conquer(int list[], int num) {
if (num <= 2) {
if (num == 2 && list[0] > list[1]) {
swap(list[0], list[1]);
}
return;
}
int mid = num / 2;
int* left = new int[mid];
int* right = new int[num - mid];
int index_l = 0, index_r = 0;
for (int i = 0; i < num; i++) {
if (i < mid) {
left[index_l] = list[i];
index_l++;
}
else {
right[index_r] = list[i];
index_r++;
}
}
divide_conquer(left, mid);
divide_conquer(right, num-mid);
index_l = 0;
index_r = 0;
for (int i = 0; i < num; i++) {
if (index_l < mid && index_r < (num - mid)) {
if (left[index_l] < right[index_r]) {
list[i] = left[index_l];
index_l++;
}
else {
list[i] = right[index_r];
index_r++;
}
}
else if (index_r < (num - mid)) {
list[i] = right[index_r];
index_r++;
}
else if (index_l < mid) {
list[i] = left[index_l];
index_l++;
}
}
delete[] left;
delete[] right;
}
????
6.快速排序
????????快速排序是对冒泡排序的一种改进。
????????通过数据分割将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以 递归 进行，以此达到整个数据变成有序序列。
????????代码：
7.堆排序
????????堆排序通过使用二叉树的方法进行排序
????????该二叉树的数据分类有一定的逻辑性。在堆的数据结构中，堆中的最大值总是位于根节点(在优先队列中使用堆的话堆中的最小值位于根节点)。再将位于根节点处的值与它的子夜节点比较，进行值的替换，使根节点的最值往下沉底，此时交换后的根节点的值就是我们需要排序的值的次序，将根节点的值与沉底的值进行交换，再将该节点断开，进行下一次的比较。
8.希尔排序
????????也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。????????
void shell_sort(int array[], int length) {
int h = 1;
while (h < length / 3) {
h = 3 * h + 1;
}
while (h >= 1) {
for (int i = h; i < length; i++) {
for (int j = i; j >= h && array[j] < array[j - h]; j -= h) {
swap(array[j], array[j - h]);
}
}
h = h / 3;
}
}
9.桶排序
????????桶排序是计数排序的升级版?。
????????工作的原理是将数组分到有限数量的桶里。每个桶再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序），最后依次把各个桶中的记录列出来记得到有序序列。? ? ? ?
????????该方法使用使用链表实现，在分类过程中，对于整除时的数采取加一个常数的算法，来减轻因int型计算丢失的问题，但这种常数取值在某些情况可能是不适用的。所以对于分区的方法仍然是需要优化的。
#define size 5
struct linknode {
linknode* next;
int data;
};
struct link {
linknode* head;
int length;
};
void FreeSpace(link* arr) {
if (arr == NULL) {
return;
}
int i = 0;
while (i != size) {
linknode* pCurrent = arr[i].head;
while (pCurrent != NULL) {
linknode* pnext = pCurrent->next;
delete pCurrent;
pCurrent = pnext;
}
arr->length = 0;
i++;
}
delete[] arr;
}
void insert(link* list, int num) {
linknode* pcurrent = list->head;
while(pcurrent->next != NULL) {
pcurrent = pcurrent->next;
}
linknode* pnext = new linknode;
pnext->data = num;
pnext->next = NULL;
pcurrent->next = pnext;
list->length += 1;
}
void listprint(link* list) {
linknode* pcurrent = list->head->next;
while (pcurrent != NULL) {
cout << pcurrent->data << endl;
pcurrent = pcurrent->next;
}
}
void initlist(link* p) {
p->head = new linknode;
p->head->next = NULL;
p->length = 0;
p->head->data = 0;
}
void bucket(int list[], int num) { //获取的list[]是一个指针，而不是一个数组空间，不可以求长度
int min = 999, max = -1;
for (int i = 0; i < num; i++) {
if (min > list[i]) min = list[i];
if (max < list[i]) max = list[i];
}
link *arr = new link[size];
for (int i = 0; i < size; i++) {
initlist(&arr[i]);
}
for (int i = 0; i < num; i++) {
for (int j = 0; j < size; j++) {
int l = min + (max - min) / size * j;
int r = min + (max - min) / size * (j + 1) + 3; // 整除因为是int形，会导致最大值丢失
if (list[i] >= l && list[i] <= r) {
insert(&arr[j], list[i]);
break;
}
}
}
int index = 0;
for (int i = 0; i < size; i++) {
linknode* pcurrent = arr[i].head->next;
while (pcurrent != NULL) {
linknode* pnext = pcurrent->next;
while (pnext != NULL) {
if (pnext->data < pcurrent->data) swap(pnext->data, pcurrent->data);
pnext = pnext->next;
}
pcurrent = pcurrent->next;
}
pcurrent = arr[i].head->next;
while (pcurrent != NULL) {
list[index] = pcurrent->data;
index++;
pcurrent = pcurrent->next;
}
}
FreeSpace(arr);
}
10.基数排序
????????代码：
|