// 交换函数
void swap(int *a, int *b)
{
int m = *a;
*a = *b;
*b = m;
}
// 冒泡排序
/* 冒泡排序（Bubble Sort，台湾译为：泡沫排序或气泡排序）是一种简单的排序算法。
它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。
走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
冒泡排序对n个项目需要O(n2)的比较次数，且可以原地排序。尽管这个算法是
最简单了解和实作的排序算法之一，但它对于少数元素之外的数列排序是很没有效率的。
冒泡排序是与插入排序拥有相等的执行时间，但是两种法在需要的交换次数却很大地不同。
在最坏的情况，冒泡排序需要O(n2)次交换，而插入排序只要最多O(n)交换。
天真的冒泡排序实作（类似下面）通常会对已经排序好的数列拙劣地执行（O(n2)），
而插入排序在这个例子只需要O(n)个运算。因此很多现代的算法教科书避免使用冒泡排序，
而用插入排序取代之。冒泡排序如果能在内部循环第一次执行时，使用一个旗标来表示有
无需要交换的可能，也有可能把最好的复杂度降低到O(n)。在这个情况，在已经排序号的
数列就无交换的需要。若在每次走访数列时，把走访顺序和比较大小反过来，也可以些微
地改进效率。有时候称为往返排序（en:shuttle sort），因为算法会从数列的一端到另一
端之间穿梭往返。
冒泡排序算法的运作如下：
比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
由于它的简洁，冒泡排序通常被用来对于程式设计入门的学生介绍算法的概念。
*/
void bubble_sort(int *arr, int len)
{
int tmp = 0;
for(int i = len -1; i > 0; i --)
{
for(int j = i - 1; j > 0; j --)
{
if(*(arr + i) < *(arr + j))
{
swap(arr+i, arr +j);
}
}
}
}
/* 鸡尾酒排序，也就是定向冒泡排序, 鸡尾酒搅拌排序, 搅拌排序 (也可以视作选择排序的一种变形),
涟漪排序, 来回排序 or 快乐小时排序, 是冒泡排序的一种变形。此算法与冒泡排序的不同处在于排序
时是以双向在序列中进行排序。
*/
void cocktail_sort(int *arr, int len)
{
int top = 0, bottom = len -1;
int _swap = 1;
int tmp = 0;
while(_swap)
{
_swap = 0;
for(int i = bottom; i > top; i --)
{
if(arr[bottom] < arr[i])
{
swap(&arr[bottom], &arr[i]);
_swap = 1;
}
}
bottom --;
for(int i = top; i < bottom; i ++)
{
if(arr[top] > arr[i])
{
swap(&arr[top], &arr[i]);
_swap = 1;
}
}
top ++;
}
}
void even_odd_sort(int * arr, int len)
{
int tmp = 0;
for(int i = len -1 ; i > len/2 -1 ; i--)
{
for(int j = 1; j < i; j += 2)
{
if(arr[j] > arr[j + 1])
swap(&arr[j], &arr[j +1]);
}
for(int j = 0; j < i; j += 2)
{
if(arr[j] > arr[j + 1])
swap(&arr[j], &arr[j +1]);
}
}
}
// 快速排序
void quick_sort(int * arr, int beg, int end)
{
if(end > beg + 1)
{
int piv = arr[beg], k = beg +1, r = end;
while(r > k)
{
if(arr[k] < piv)
k++;
else
swap(&arr[k], &arr[r--]);
}
if(arr[k] < piv) // 如果剩下的那个数比标记小，则交换，这样就是这个数前面的都比它小，后面的都比它大，所以这个数就不用再排了。
{
swap(&arr[k], &arr[beg]);
quick_sort(arr, beg, k - 1);
quick_sort(arr, k + 1, end);
}
else // 如果剩下这个数大于或等于标记的数，那么将这个数的前一个与这个数交换，并对之前的和之后的分别排序。
{
if(end - beg == 1)
return;
swap(&arr[--k], &arr[beg]);
quick_sort(arr, beg, k);
quick_sort(arr, k + 1, end);
}
}
}
// 选择排序
void select_sort(int *arr, int len)
{
for(int i = 0; i < len; i++)
{
for(int j = i + 1; j < len; j ++)
{
if(arr[i] > arr[j])
swap(&arr[i], &arr[j]);
}
}
}
// 堆排序
static void build_heap(int *arr, int start, int end)
{
int parent = start;
int tmp = arr[start];
int child = (start << 1) + 1;
//i = start << 1; // the child of start;
while(child <= end)
{
if(child < end)
{
if(arr[child] < arr[child + 1]) // 如果左子节点比右指节点小，则不管左子节点
child ++;
}
if(arr[child] < tmp)
{
break;
}
else
{
//swap(arr + start, arr + i);
arr[parent] = arr[child];
parent = child;
child = (child << 1) + 1;
}
}
arr[parent] = tmp;
}
void heap_sort(int * arr, int len)
{
int i;
for(i = (len >> 1) -1; i >= 0; i --)
build_heap(arr, i, len -1);
for(i = len -1; i >= 0; i--)
{
swap(arr + i, arr);
build_heap(arr, 0, i -1);
}
}
// 插入排序
void insert_sort(int * arr, int len)
{
int tmp = 0;
int j = 0;
for(int i = 1; i < len; i++)
{
tmp = arr[i];
for(j = i; j > 0; j --)
{
if(tmp < arr[j -1])
*(arr + j) = *(arr + j -1);
else
{
break;
}
}
arr[j] = tmp;
}
}
// 希尔排序
void shell_sort(int * arr, int len)
{
int step = len /2;
int tmp = 0;
int i = 0;
int j = 0;
while(step)
{
for(i = step; i < len; i += step)
{
j = i - step;
tmp = arr[i];
while(j >= 0 && tmp < arr[j])
{
arr[j + step] = arr[j];
j -= step;
}
arr[j + step] = tmp;
}
step >>= 1;
}
}
// 归并排序
static void merge(int * arr, int start, int mid, int end)
{
int * sa1 = (int *)malloc(sizeof(int) *(end - start + 1));
memcpy(sa1, arr + start, sizeof(int) *(end - start + 1));
int *sa2 = arr + mid + 1;
int len1 = mid -start +1;
int len2 = end - mid;
int i = 0, j = 0, k = start;
while(i < len1 && j < len2)
{
if(sa1[i] < sa2[j])
arr[k ++] = sa1[i ++];
else
arr[k ++] = sa2[j ++];
}
while(i < len1)
{
arr[k ++] = sa1[i ++];
}
while(j < len2)
{
arr[k ++] = sa2[j ++];
}
free(sa1);
}
void merge_sort(int * arr, int start, int end)
{
if(start < end)
{
//int * p = (int *)malloc(sizeof(int) * (end - start + 1));
//memcpy(p, arr, sizeof(int) * (end - start + 1));
int mid = (start + end) / 2;
merge_sort(arr, start, mid);
merge_sort(arr, mid + 1, end);
merge(arr, start , mid, end);
//free(p);
}
}
|
