冒泡排序 Bubble Sort
基本思想：交换排序，两两比较相邻记录的关键字，如果反序则交换，知道没有反序的记录为止。
(对相邻的元素进行两两比较，顺序相反则进行交换)
原始版：
#include <stdio.h>
void BubbleSort(int a[], int n)
{
for(int i=0; i<n; ++i)
{
for(int j= n-2; j>=i; --j)
{
if(a[j] > a[j+1])
swap(a[j], a[j+1]);
}
}
}
int main()
{
int a[] = {50, 10, 90, 30, 70, 40, 80, 60, 20};
//int a[] = {4, 10, 3, 5, 1, 2};
int n = sizeof(a)/sizeof(a[0]);
BubbleSort(a, n);
for(int i=0; i<n; ++i)
printf("%d\n",a[i]);
return 0;
}
改进版：
#include <stdio.h>
void BubbleSort2(int a[], int n)
{
bool flag = true;
for(int i=0; i<n && flag; ++i)
{
flag = false;
for(int j= n-2; j>=i; --j)
{
if(a[j] > a[j+1])
{
swap(a[j], a[j+1]);
flag = true;
}
}
}
}
int main()
{
int a[] = {50, 10, 90, 30, 70, 40, 80, 60, 20};
//int a[] = {4, 10, 3, 5, 1, 2};
int n = sizeof(a)/sizeof(a[0]);
BubbleSort2(a, n);
for(int i=0; i<n; ++i)
printf("%d\n",a[i]);
return 0;
}
| 比较次数 | 数据交换 | 时间复杂度 | |
|---|---|---|---|
| 最好情况 | n-1 | 0 | O(n) |
| 最坏情况 | n(n-1)/2 | n(n-1)/2 | O(n^2) |
简单选择排序 Simple Selection Sort
通过n-i次关键字之间的比较，在n-i+1个记录中选出关键字最小的记录，并和第i个记录交换之
#include <stdio.h>
void SelectionSort(int a[], int n)
{
int min;
for(int i=0; i<n; ++i)
{
min = i;
for(int j=i+1; j<n; ++j)
{
if(a[min] > a[j])
min = j;
}
if(min != i)
swap(a[i],a[min]);
}
}
int main()
{
int a[] = {50, 10, 90, 30, 70, 40, 80, 60, 20};
//int a[] = {4, 10, 3, 5, 1, 2};
int n = sizeof(a)/sizeof(a[0]);
SelectionSort(a, n);
for(int i=0; i<n; ++i)
printf("%d\n",a[i]);
return 0;
}
| 比较次数 | 数据交换 | 时间复杂度 | |
|---|---|---|---|
| 最好情况 | n(n-1)/2 | 0 | O(n^2) |
| 最坏情况 | n(n-1)/2 | n-1 | O(n^2) |
直接插入排序 Straight Insertion Sort
将一个记录插入到已经排序好的有序表中，从而得到一个新的、记录数增1的有序表
#include <stdio.h>
void InsertSort(int a[], int n)
{
int tmp, j;
for(int i=1; i<n; ++i)
{
tmp = a[i];
for(j=i-1; j>=0 && a[j]>tmp; --j)
{
a[j+1] = a[j];
}
a[j+1] = tmp;
}
}
int main()
{
int a[] = {50, 10, 90, 30, 70, 40, 80, 60, 20};
//int a[] = {4, 10, 3, 5, 1, 2};
int n = sizeof(a)/sizeof(a[0]);
InsertSort(a, n);
for(int i=0; i<n; ++i)
printf("%d\n",a[i]);
return 0;
}
| 比较次数 | 数据交换 | 时间复杂度 | |
|---|---|---|---|
| 最好情况 | n-1 | 0 | O(n) |
| 最坏情况 | (n+2)(n-1)/2 | (n+4)(n-1)/2 | O(n^2) |
| 平均情况 | (n^2)/4 | (n^2)/4 | O(n^2) |
希尔排序 Shell Sort
希尔排序实际上是一种特殊的插入排序
将相距某个“增量”的记录组成一个子序列，保证在子序列内分别进行直接插入排序后得到的结果是基本有序而不是局部有序
#include <stdio.h>
void ShellSort(int a[], int n)
{
int increment = n;
int j;
do
{
increment = increment/3+1;
for(int i=increment; i<n; ++i)
{
int tmp = a[i];
for(j=i-increment; j>=0 && a[j]>tmp; j-=increment)
{
a[j+increment] = a[j];
}
a[j+increment] = tmp;
}
}
while(increment>1);
}
int main()
{
int a[] = {50, 10, 90, 30, 70, 40, 80, 60, 20};
//int a[] = {4, 10, 3, 5, 1, 2};
int n = sizeof(a)/sizeof(a[0]);
ShellSort(a, n);
for(int i=0; i<n; ++i)
printf("%d\n",a[i]);
return 0;
}
时间复杂度O(n^(3/2))
归并排序 Merging Sort
最好、最坏与平均时间复杂度：O(nlogn)
空间复杂度：O(n+logn)
稳定的排序
递归方法：
#include <stdio.h>
#define MAX 100
void Merge(int tmp[], int des[], int low, int mid, int high)
{
int i = low, j = mid + 1, k = low;
while((i<=mid) && (j<=high))
{
if(tmp[i]<tmp[j])
des[k++] = tmp[i++];
else
des[k++] = tmp[j++];
}
while(i <= mid)
{
des[k++] = tmp[i++];
}
while(j <= high)
{
des[k++] = tmp[j++];
}
}
void MSort(int src[], int des[], int low, int high)
{
if(low == high)
des[low] = src[low];
else
{
int tmp[MAX];
int mid = (low + high)/2;
MSort(src, tmp, low, mid);
MSort(src, tmp, mid+1, high);
Merge(tmp, des, low, mid, high);
}
}
void MergeSort(int a[], int len)
{
MSort(a, a, 0, len-1);//下标
}
int main()
{
int a[] = {50, 10, 90, 30, 70, 40, 80, 60, 20};
//int a[] = {4, 10, 3, 5, 1, 2};
int len = sizeof(a)/sizeof(*a);
MergeSort(a, len);
for(int i=0; i<len; ++i)
printf("%d\n",a[i]);
return 0;
}
堆排序 Heap Sort
堆排序是一种选择排序，整体主要由构建初始堆+交换堆顶元素和末尾元素并重建堆两部分组成。其中构建初始堆经推导复杂度为O(n)，在交换并重建堆的过程中，需交换n-1次，而重建堆的过程中，根据完全二叉树的性质，[log2(n-1),log2(n-2)…1]逐步递减，近似为nlogn。所以堆排序时间复杂度一般认为就是O(nlogn)级。
代码一
#include <stdio.h>
void swap(int arr[], int i, int j)
{
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
void heapify(int tree[] , int n, int i) //堆化，堆调整
{
if(i >= n)
return;
int c1 = 2*i + 1;
int c2 = 2*i + 2;
int max = i;
if(c1 < n && tree[c1] > tree[max])
max = c1;
if(c2 < n && tree[c2] > tree[max])
max = c2;
if(max != i)
{
swap(tree, max, i);
heapify(tree, n, max);
}
}
void build_heap(int tree[], int n) //建立堆
{
int last_node = n - 1;
int first = (last_node - 1)/2;
for(int i=first; i>=0; --i)
heapify(tree, n, i);
}
void HeapSort(int tree[], int n) //堆排序
{
build_heap(tree, n);
for(int i=n-1; i>=0; --i)
{
swap(tree, i, 0);
heapify(tree, i, 0);
}
}
int main()
{
int tree[] = {50, 10, 90, 30, 70, 40, 80, 60, 20};
//int tree[] = {4, 10, 3, 5, 1, 2};
int n = sizeof(tree)/sizeof(*tree);
HeapSort(tree, n);
for(int i=0; i<n; ++i)
printf("%d\n",tree[i]);
return 0;
}
运行时间主要是消耗在初始构建堆和在重建堆时的反复筛选上。
对于每个非终端节点，最多进行两次比较和互换操作，构建堆的时间复杂度O(n)
重建堆的时间复杂度O(nlogn)
最好、最坏和平均时间复杂度：O(nlogn)
不稳定
代码二
#include <stdio.h>
void swap(int arr[], int i, int j)
{
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
void HeapAdjust(int tree[], int index, int len)
{
int tmp = tree[index];
for (int j = 2*index + 1; j < len; j = 2*j + 1) {
if (j + 1 < len && tree[j] < tree[j + 1])
++j;
if (tmp > tree[j])
break;
tree[index] = tree[j];
index = j;
}
tree[index] = tmp;
}
void HeapSort(int tree[], int len)
{
//首先构建初始堆，每个元素的值大于其左右子树
for (int i = len/2 -1; i >= 0 ;--i)
HeapAdjust(tree, i, len);
/* 之后将堆顶元素（即最大元素）与末尾元素交换 */
/* 排除末尾元素，让剩下的元素重新构造堆 */
for (int i = len -1; i > 0; --i) {
swap(tree, 0 , i);
HeapAdjust(tree, 0, i);
}
}
int main()
{
//int tree[] = {50, 10, 90, 30, 70, 40, 80, 60, 20};
int tree[] = {4, 10, 3, 5, 1, 2};
int len = sizeof(tree)/sizeof(tree[0]);
HeapSort(tree, len);
for (int i=0; i < len; ++i)
printf("%d\n", tree[i]);
return 0;
}
快速牌序 Quick Sort
冒泡排序的升级，交换排序。
基本思想：通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键子均比另一部分记录的关键字小，则可分别对这两部分记录进行排序，以达到整个序列有序的目的。
代码一
#include <stdio.h>
int partition(int a[], int low, int high)
{
int key = a[low];
while(low<high)
{
while(low<high && a[high]>=key)
--high;
swap(a[high], a[low]);
while(low<high && a[low]<=key)
++low;
swap(a[high], a[low]);
}
return low;
}
void QSort(int a[], int low, int high)
{
int pivot;
if(low < high)
{
pivot = partition(a, low, high);
QSort(a, low, pivot-1);
QSort(a, pivot+1, high);
}
}
void QuickSort(int a[], int n)
{
QSort(a, 0, n-1);
}
int main()
{
int a[] = {50, 10, 90, 50, 70, 40, 80, 60, 20};
//int a[] = {4, 10, 3, 5, 1, 2};
int n = sizeof(a)/sizeof(a[0]);
QuickSort(a, n);
for(int i=0; i<n; ++i)
printf("%d\n",a[i]);
return 0;
}
改进版
#include <stdio.h>
int partition(int a[], int low, int high)
{
// 三数取中
int m = (high - low)/2 + low;
if(a[low] > a[high])
swap(a[low], a[high]);
if(a[m]> a[high])
swap(a[m], a[high]);
if(a[m] > a[low])
swap(a[m], a[low]);
int key = a[low];
int tmp = key;
while(low<high)
{
while(low<high && a[high]>=key)
--high;
a[low] = a[high];
while(low<high && a[low]<=key)
++low;
a[high] = a[low];
}
a[low] = tmp;
return low;
}
void QSort(int a[], int low, int high)
{
int pivot;
if(low<high)
{
pivot = partition(a, low, high);
QSort(a, low, pivot-1);
QSort(a, pivot+1, high);
}
}
void QuickSort(int a[], int n)
{
QSort(a, 0, n-1);
}
int main()
{
int a[] = {50, 10, 90, 50, 70, 40, 80, 60, 20};
//int a[] = {4, 10, 3, 5, 1, 2};
int n = sizeof(a)/sizeof(a[0]);
QuickSort(a, n);
for(int i=0; i<n; ++i)
printf("%d\n",a[i]);
return 0;
}
链表排序
单链表的归并排序：时间复杂度O(nlogn)，空间复杂度O(1)
利用归并排序：
#include <bits/stdc++.h>
using namespace std;
struct ListNode
{
int val;
ListNode* next;
ListNode(int x):val(x),next(NULL){}
};
ListNode* MergeList(ListNode* headA, ListNode* headB)
{
ListNode *newhead = new ListNode(0);
ListNode *tail = newhead;
while(headA != NULL && headB != NULL)
{
if(headA->val < headB->val)
{
tail->next = headA;
tail = headA;
headA = headA->next;
}
else
{
tail->next = headB;
tail = headB;
headB = headB->next;
}
}
while(headA != NULL)
{
tail->next = headA;
tail = headA;
headA = headA->next;
}
while(headB != NULL)
{
tail->next = headB;
tail = headB;
headB = headB->next;
}
ListNode* rehead = newhead->next;
delete newhead;
return rehead;
}
ListNode* MsortList(ListNode* head)
{
if(head == NULL || head->next == NULL)
return head;
ListNode *slow = head;
ListNode *fast = head->next;
while(fast != NULL && fast->next != NULL) //找到中间节点，再分半
{
slow = slow->next;
fast = fast->next->next;
}
ListNode *h2 = slow->next;
slow->next = NULL;
ListNode *p1 = MsortList(head); //递归
ListNode *p2 = MsortList(h2); //递归
return MergeList(p1, p2);
}
int main()
{
ListNode *head = new ListNode(4);
head->next = new ListNode(2);
head->next->next = new ListNode(1);
head->next->next->next = new ListNode(3);
head->next->next->next->next = new ListNode(6);
head->next->next->next->next->next = new ListNode(5);
head = MsortList(head);
while(head != NULL)
{
cout<<head->val<<endl;
head = head->next;
}
return 0;
}