排序算法的差异
排序算法归纳
算法（基于C实现）
1.冒泡排序
思路：在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。
void bubble_sort(int *r, int n){
int k,temp;
for (int i = 0; i < n-1; i++) {
k = 0;
for (int j = 0; j < n-i-1; j++) {
if (*(r+j+1) < *(r+j)) {
temp = *(r+j+1);
*(r+j+1) = *(r+j);
*(r+j) = temp;
k++;
}
}
if (k == 0) {
break;
}
}
}
2.直接插入排序
思路：在要排序的一组数中，假设前面(n-1)[n>=2]个数已经是排好顺序的，现在要把第n个数插到前面的有序数中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。
void insert_sort(int *r, int n){
int j,temp;
for (int i = 1; i < n; i++) {
temp = *(r+i);
for (j = i - 1; *(r+j) > temp && j >= 0 ; j--) {
*(r+j+1) = *(r+j);
}
*(r+j+1) = temp;
}
}
3.归并排序
思路：略
void merge_sort(int *r, int n){
int reg[n];
merge_sort_recursive(r, reg, 0, n - 1);
}
void merge_sort_recursive(int arr[], int reg[], int start, int end) {
if (start >= end)
return;
int len = end - start, mid = (len >> 1) + start;
int start1 = start, end1 = mid;
int start2 = mid + 1, end2 = end;
merge_sort_recursive(arr, reg, start1, end1);
merge_sort_recursive(arr, reg, start2, end2);
int k = start;
while (start1 <= end1 && start2 <= end2)
reg[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
while (start1 <= end1)
reg[k++] = arr[start1++];
while (start2 <= end2)
reg[k++] = arr[start2++];
for (k = start; k <= end; k++)
arr[k] = reg[k];
}
4.二分排序
思路：略
void bin_sort(int *r, int n){
int head,tail,mid,temp;
for (int i = 1; i<n; i++) {
temp = *(r+i);
head = 0,tail = i - 1;
for (; head<=tail; ) {
mid = (head+tail)/2;
if (*(r+mid)>temp)
tail = mid - 1;
else
head = mid + 1;
}
for (int j = i -1; j >= head; j--)
*(r+j+1) = *(r+j);
*(r+head) = temp;
}
}
5.直接选择排序
思路： 在要排序的一组数中，选出最小的一个数与第一个位置的数交换；然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。
void select_sort(int *r, int n){
int min,temp;
for (int i = 0; i < n; i++) {
min = i;
for (int j = i; j < n; j++) {
if (*(r+j) < *(r+min)) {
min = j;
}
}
if (min != i) {
temp = *(r+min);
*(r+min) = *(r+i);
*(r+i) = temp;
}
}
}
6.快速排序
思路： 快速排序是对冒泡排序的一种本质改进。它的基本思想是通过一趟扫描后，使得排序序列的长度能大幅度地减少。在冒泡排序中，一次扫描只能确保最大数值的数移到正确位置，而待排序序列的长度可能只减少1。快速排序通过一趟扫描，就能确保某个数（以它为基准点吧）的左边各数都比它小，右边各数都比它大。然后又用同样的方法处理它左右两边的数，直到基准点的左右只有一个元素为止。它是由C.A.R.Hoare于1962年提出的。
void quick_sort(int *r, int high,int low){
int temp,i,j;
if (low > high) {
return;
}
i = low,j = high,temp = *(r+i);
for (; i<j; ) {
while (temp < *(r+j) && i<j)
j--;
if (i<j) {
*(r+i) = *(r+j);
i++;
}
while (temp > *(r+i) && i<j)
i++;
if (i<j) {
*(r+j) = *(r+i);
j--;
}
}
*(r+i) = temp;
quick_sort(r, i-1, low);
quick_sort(r, high, i+1);
}
7.希尔排序
思路：在直接插入排序算法中，每次插入一个数，使有序序列只增加1个节点，并且对插入下一个数没有提供任何帮助。如果比较相隔较远距离（称为增量）的数，使得数移动时能跨过多个元素，则进行一次比较就可能消除多个元素交换。D.L.shell于1959年在以他名字命名的排序算法中实现了这一思想。算法先将要排序的一组数按某个增量d分成若干组，每组中记录的下标相差d.对每组中全部元素进行排序，然后再用一个较小的增量对它进行，在每组中再进行排序。当增量减到1时，整个要排序的数被分成一组，排序完成。
void shell_sort(int *r, int n){
int d,temp,j;
for (d = n/2; d > 0; d /= 2) {
for (int i = d; i < n; i++) {
temp = *(r+i);
for (j = i - d; j >= 0 && (temp<*(r+j)); j -= d) {
*(r+j+d) = *(r+j);
}
*(r+j+d) = temp;
}
}
}
8.堆排序
思路：堆排序是一种树形选择排序，是对直接选择排序的有效改进。堆的定义如下：具有n个元素的序列（h1,h2,...,hn),当且仅当满足（hi>=h2i,hi>=2i+1）或（hi<=h2i,hi<=2i+1）(i=1,2,...,n/2)时称之为堆。在这里只讨论满足前者条件的堆。由堆的定义可以看出，堆顶元素（即第一个元素）必为最大项。完全二叉树可以很直观地表示堆的结构。堆顶为根，其它为左子树、右子树。初始时把要排序的数的序列看作是一棵顺序存储的二叉树，调整它们的存储顺序，使之成为一个堆，这时堆的根节点的数最大。然后将根节点与堆的最后一个节点交换。然后对前面(n-1)个数重新调整使之成为堆。依此类推，直到只有两个节点的堆，并对它们作交换，最后得到有n个节点的有序序列。
从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数，二是反复调用渗透函数实现排序的函数。
void sift(int *r, int n, int s){
int temp,j,i;
temp = *(r+s);
i = s;
j = 2*i+1;
for (; j <= n; ) {
if (j<n&&*(r+j+1)<*(r+j)) {
j++;
}
if (temp>*(r+j)) {
*(r+i) = *(r+j);
i = j;
j = 2*j+1;
}else
break;
}
*(r+i) = temp;
}
void heap_sort(int *r, int n){
int temp,i;
for (i = n/2-1; i >= 0; i--)
sift(r, n-1, i);
for (int k = n-1; k>0; k--) {
temp = *r;
*r = *(r+k);
*(r+k) = temp;
sift(r, k - 1, 0);
}
}
网友评论