/*
冒泡排序
算法思想：将被排序的记录数组R[1..n]垂直排列，每个记录R看作是重量为R.key的气泡。 根据轻气泡不能在重气泡之下的原则，从下往上扫描数组 R：凡扫描到违反本原则的 轻气泡，就使其向上"飘浮"。如此反复进行，直到最后任何两个气泡都是轻者在上， 重者在下为止。
时间复杂度 o(n^2)
空间复杂度 o(1)
比较次数 n(n+1)/2
*/
void bubble_sort(int array[],int len)
{
for (int i = len-1 ;i >= 0;i-- )
{
for(int j = 0;j < i;j++)
if(array[j] > array[j+1])
swap(array[j],array[j+1]);
}
}
/*
直接插入排序
算法思想：把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，将它 插入到有序表中的适当位置，使之成为新的有序表，重复n-1次可完成排序过程。
时间复杂度 o(n^2)
空间复杂度 o(1)
比较次数 n(n+1)/2
*/
void insert_sort(int array[],int len)
{
int tmp,i,j;
for(i = 1;i < len;i++)
{
if (array < array[i-1])
{
tmp = array;
array = array[i-1];
//插入到相应位置
for (j = i-2;j >= 0;j--)
{
//往后移
if (array[j] > tmp )
array[j+1] = array[j];
else
{
array[j+1] = tmp;
break;
}
}
if(j == -1)
array[j+1] = tmp;
}
}
}
/*
二路插入排序
算法思想：增加一个辅助空间d,把r[1]赋值给d[1]，并将d[1]看成是排好序后处于中间 位置的记录。然后从r[2]开始依次插入到d[1]之前或之后的有序序列中。
时间复杂度 o(n^2)
空间复杂度 o(1)
比较次数 n(n+1)/2
*/
void bi_insert_sort(int array[],int len)
{
int* arr_d = (int *)malloc(sizeof(int) * len);
arr_d[0] = array[0];
int head = 0,tail = 0;
for (int i = 1;i < len; i++ )
{
if (array > arr_d[0])
{
int j;
for ( j= tail;j>0;j--)
{
if (array < arr_d[j])
arr_d[j+1] = arr_d[j];
else
break;
}
arr_d[j+1] = array;
tail += 1;
}
else
{
if (head ==0)
{
arr_d[len-1] = array;
head =len-1;
}
else
{
int j;
for (j = head;j <= len-1;j++)
{
if (array > arr_d[j])
arr_d[j-1] = arr_d[j];
else
break;
}
arr_d[j-1] = array;
head -= 1;
}
}
}
for (int i = 0;i < len; i++)
{
int pos = (i + head );
if(pos >= len) pos -= len;
array = arr_d[pos];
}
free(arr_d);
}
/*
希尔排序
算法思想：先将整个待排序记录分割成若干子序列分别进行直接插入排 序，待整个序列中的记录基本有序时，再对全体记录进行一次直接插入排序。
时间复杂度 o(n^2)
空间复杂度 o(1)
比较次数 ?
*/
void shell_insert(int array[],int d,int len)
{
int tmp,j;
for (int i = d;i < len;i++)
{
if(array < array[i-d])
{
tmp = array;
j = i - d;
do
{
array[j+d] = array[j];
j = j - d;
} while (j >= 0 && tmp < array[j]);
array[j+d] = tmp;
}
}
}
void shell_sort(int array[],int len)
{
int inc = len;
do
{
inc = inc/2;
shell_insert(array,inc,len);
} while (inc > 1);
}
/*
快速排序
算法思想：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合成为原问题的解。
时间复杂度 o(nlogn)
空间复杂度 o(logn)
比较次数 ?
*/
int partition(int array[],int low,int high)
{
int pivotkey = array[low];
while (low < high)
{
while(low < high && array[high] >= pivotkey)
--high;
swap(array[low],array[high]);
while(low < high && array[low] <= pivotkey)
++low;
swap(array[low],array[high]);
}
array[low] = pivotkey;
return low;
}
void quick_sort(int array[],int low,int high)
{
if (low < high)
{
int pivotloc = partition(array,low,high);
quick_sort(array,low,pivotloc-1);
quick_sort(array,pivotloc+1,high);
}
}
/*
直接选择排序
算法思想：每一趟在n-i+1个记录中选取关键字最小的记录作为有序序列中的第i个记录。
时间复杂度 o(n^2)
空间复杂度 o(1) ?
比较次数 n(n+1)/2
*/
int SelectMinKey(int array[],int iPos,int len)
{
int ret = 0;
for (int i = iPos; i < len; i++)
{
if (array[ret] > array)
{
ret = i;
}
}
return ret;
}
void select_sort(int array[],int len)
{
for (int i = 0; i < len; i++)
{
int j = SelectMinKey(array,i,len);
if (i != j)
{
swap(array,array[j]);
}
}
}
/*
归并排序
算法思想：设两个有序的子文件(相当于输入堆)放在同一向量中相邻的位置上：R[low..m]，R[m+1..high]，先 将它们合并到一个局部的暂存向量R1(相当于输出堆)中，待合并完成后将R1复制回R[low..high]中。
时间复杂度 o(nlogn)
空间复杂度 o(n)
比较次数 ?
*/
void merge(int array[],int i,int m, int n)
{
int j,k;
int iStart = i, iEnd = n;
int arrayDest[256];
for ( j = m + 1,k = i; i <= m && j <= n; ++k)
{
if (array < array[j])
arrayDest[k] = array[i++];
else
arrayDest[k] = array[j++];
}
if (i <= m)
for (;k <= n; k++,i++)
arrayDest[k] = array;
if(j <= n)
for (;k <= n; k++,j++)
arrayDest[k] = array[j];
for(j = iStart; j <= iEnd; j++)
array[j] = arrayDest[j];
}
void merge_sort(int array[],int s,int t)
{
int m;
if (s < t)
{
m = (s + t )/2;
merge_sort(array,s,m);
merge_sort(array,m+1,t);
merge(array,s,m,t);
}
}
/*
堆排序
算法思想：堆排序（Heap Sort）是指利用堆（heaps）这种数据结构来构造的一种排序算法。 堆是一个近似完全二叉树结构，并同时满足堆属性：即子节点的键值或索引总是
小于（或者大于）它的父节点。
时间复杂度 o(nlogn)
空间复杂度 o(1)
比较次数 较多
*/
void heap_adjust(int array[],int i,int len)
{
int rc = array;
for(int j = 2 * i; j <len; j *= 2)
{
if(j < len && array[j] < array[j+1]) j++;
if(rc >= array[j]) break;
array = array[j]; i = j;
}
array = rc;
}
void heap_sort(int array[],int len)
{
int i;
for(i = (len-1)/2; i >= 0; i--)
heap_adjust(array,i,len);
for( i = (len-1); i > 0; i--)
{
swap(array[0],array); //弹出最大值，重新对i-1个元素建堆
heap_adjust(array,0,i-1);
}
}
int main() {
int array[] = {45,56,76,234,1,34,23,2,3,55,88,100};
int len = sizeof(array)/sizeof(int);
//bubble_sort(array,len); //冒泡排序
/*insert_sort(array,len);*/ //插入排序
/*bi_insert_sort(array,len);*/ //二路插入排序
/*shell_sort(array,len);*/ //希尔排序
/*quick_sort(array,0,len-1);*/ //快速排序
/*select_sort(array,len);*/ //选择排序
/*merge_sort(array,0,len-1);*/ //归并排序
heap_sort(array,len); //堆排序
display(array,len);
return 0;
}
我们知道堆的结构是节点i的孩子为2*i和2*i+1节点，大顶堆要求父节点大于等于其2个子节点，小顶堆要求父节点小于等于其2个子节点。在一个长为n 的序列，堆排序的过程是从第n/2开始和其子节点共3个值选择最大(大顶堆)或者最小(小顶堆),这3个元素之间的选择当然不会破坏稳定性。但当为n /2-1, n/2-2, ...1这些个父节点选择元素时，就会破坏稳定性。有可能第n/2个父节点交换把后面一个元素交换过去了，而第n/2-1个父节点把后面一个相同的元素没 有交换，那么这2个相同的元素之间的稳定性就被破坏了。所以，堆排序不是稳定的排序算法。
| 欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) | 黑马程序员IT技术论坛 X3.2 |