|
|
一、快速排序
|
|
|
1.1 算法思想
|
|
|
先从数列中取出一个数作为key 值；将比这个数小的数全部放在它的左边，大于或等于它的数全部放在它的右边；对左右两个小数列重复上一步，直至各区间只有 1 个数。
|
|
|
1.2 复杂程度
|
|
|
复杂程度：O( nlog(2n) ).
|
|
|
1.3程序
|
|
|
一次快速排序的算法的步骤如下：
|
|
|
1）设置两个变量 i、j，排序开始时 i=0、j=N-1。
|
|
|
2）以第一个数组元素 a[0]（即a[i]）作为基准元素。
|
|
|
3）从 j 开始从后往前搜索 (j--)，找到第一个小于 a[i] 的数 a[j]，将 a[j] 和 a[i] 互换位置，此时基准元素的位置在数组的第 j 个位置。
|
|
|
4）从 i 开始从前向后搜索 (i++)，找到第一个大于 a[j] 的 a[i]，将 a[i] 和 a[j] 互换位置，此时基准元素的位置在数组的第 i个位置。
|
|
|
5）重复 3、4，直到 i=j，此时循环结束
|
|
|
#include<stdio.h>
|
|
|
void sort(int a[],int left ,int right)
|
|
|
{
|
|
|
int i,j,temp;
|
|
|
i=left;
|
|
|
j=right;
|
|
|
temp=a[left];
|
|
|
if(left>right) return;
|
|
|
while(i != j) //i不等于j时，循环进行
|
|
|
{
|
|
|
while(a[j] >= temp && j > i)
|
|
|
j --;
|
|
|
if(j > i)
|
|
|
a[i++]=a[j];
|
|
|
while(a[i]<=temp && j>i)
|
|
|
i++;
|
|
|
if(j>i)
|
|
|
a[j--]=a[i];
|
|
|
}
|
|
|
a[i]=temp;
|
|
|
sort(a,left,i-1); //对小于基准元素的部分进行快速排序
|
|
|
sort(a,i+1,right); //对大于基准元素的部分进行快速排序
|
|
|
}
|
|
|
int main()
|
|
|
{
|
|
|
int m[1000];
|
|
|
int n,i=0;
|
|
|
scanf(“%d”,&n);
|
|
|
for(i = 0;i < n;I ++)
|
|
|
{
|
|
|
scanf(“%d”,&m[i]);
|
|
|
}
|
|
|
sort(m,0,n - 1);
|
|
|
printf("从小到大排序后：\n");
|
|
|
for(i=0;i<n;i++)
|
|
|
printf("%d",m[i]); //输出排序结果
|
|
|
printf("\n");
|
|
|
}
|
|
|
1.4 运行时间结果
|
|
|
15 52 32 14 98 30 75 66 3 14
|
|
|
从小到大排序后:
|
|
|
3 14 14 30 32 45 52 66 75 98
|
|
|
rocess exited after 22.77 seconds with return value 10
|
|
|
清按任意键继续..
|
|
|
|
|
|
二、冒泡排序
|
|
|
2.1 算法思想
|
|
|
通过无序区中相邻记录关键字间的比较和位置的交换，使得关键字中最小的记录如“气泡”一般网上漂浮直至“水面”（这个也是冒泡名称的由来）。算法步骤：整个算法是从最下面的记录开始，对每个相邻的关键字进行比较，且使关键字较小的记录换至关键字较大的记录之上，使得每经过一趟冒泡排序以后，关键字最小的记录到达最上端，接着，再在剩下的记录中找到关键字最小的记录，并把它换在第二个位置上，每一轮到找到剩下部分的最小记录，依次类推。
|
|
|
2.2 复杂程度
|
|
|
冒泡的时间复杂度是O(N²),可以对冒泡排序进行优化,若排序的过程中,序列已变为有序,则不会进行冒泡,所以之后的排序就不用进行了,这样的话,序列越是有序,则时间复杂度会趋于O(N).
|
|
|
2.3 程序：
|
|
|
for(i=0;i<n-1;++i) //n个数,总共需要进行n-1次
|
|
|
{ //n-1个数排完,第一个数一定已经归位
|
|
|
//每次会将最大(升序)或最小(降序)放到最后面
|
|
|
int f=1; //这里设置一个开关变量
|
|
|
for(j=0;j<n-i-1;++j)
|
|
|
{
|
|
|
if(a[j]>a[j+1])
|
|
|
{
|
|
|
t=a[j];
|
|
|
a[j]=a[j+1];
|
|
|
a[j+1]=t;
|
|
|
f=0;
|
|
|
}
|
|
|
}
|
|
|
if(1==f) //f为1说明没进行过冒泡,说明序列有序
|
|
|
break; //若序列有序,则跳出排序即可
|
|
|
}
|
|
|
2.4 运行时间结果（以一道题为例）
|
|
|
#include <stdio.h>
|
|
|
int main(void)
|
|
|
{
|
|
|
int a[] = {900, 2, 3, -58, 34, 76, 32, 43, 56, -70, 35, -234, 532, 543, 2500};
|
|
|
int n,i,j,buf;
|
|
|
n = sizeof(a) / sizeof(a[0]);
|
|
|
for (i=0; i<n-1; ++i)
|
|
|
{
|
|
|
for (j=0; j<n-1-i; ++j)
|
|
|
{
|
|
|
if (a[j] < a[j+1])
|
|
|
{
|
|
|
buf = a[j];
|
|
|
a[j] = a[j+1];
|
|
|
a[j+1] = buf;
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
for (i=0; i<n; ++i)
|
|
|
{
|
|
|
printf("%d\x20", a[i]);
|
|
|
}
|
|
|
printf("\n");
|
|
|
return 0;
|
|
|
}
|
|
|
|
|
|
2500 900 543 532 76 56 43 35 34 32 3 2 -58 -70 -234
|
|
|
|
|
|
--------------------------------
|
|
|
Process exited after 0.1741 seconds with return value 0
|
|
|
请按任意键继续. . .
|
|
|
|
|
|
三、堆排序
|
|
|
3.1 算法思想
|
|
|
首先将待排序的数组构造成一个大根堆，此时，整个数组的最大值就是堆结构的顶端。将顶端的数与末尾的数交换，此时，末尾的数为最大值，剩余待排序数组个数为n-1。将剩余的n-1个数再构造成大根堆，再将顶端数与n-1位置的数交换，如此反复执行，便能得到有序数组
|
|
|
3.2 复杂程度
|
|
|
在实现过程的时候，第一阶段堆的构建最多用到2N次比较， 在取掉最大值，重新建堆的一次过程中，最多用到2logi。因此在最坏的情况下，总数最多为2NlogN-O（N）次比较。
|
|
|
3.3 代码
|
|
|
#include <stdio.h>
|
|
|
#include <stdlib.h>
|
|
|
void swap(int* a, int* b)
|
|
|
{
|
|
|
int temp = *b;
|
|
|
*b = *a;
|
|
|
*a = temp;
|
|
|
}
|
|
|
void max_heapify(int arr[], int start, int end)
|
|
|
{
|
|
|
//建立父节点指标和子节点指标
|
|
|
int dad = start;
|
|
|
int son = dad * 2 + 1;
|
|
|
while (son <= end) //若子节点指标在范围内才做比较
|
|
|
{
|
|
|
if (son + 1 <= end && arr[son] < arr[son + 1]) //先比较两个子节点大小，选择最大的
|
|
|
son++;
|
|
|
if (arr[dad] > arr[son]) //如果父节点大於子节点代表调整完毕，直接跳出函数
|
|
|
return;
|
|
|
else //否则交换父子内容再继续子节点和孙节点比较
|
|
|
{
|
|
|
swap(&arr[dad], &arr[son]);
|
|
|
dad = son;
|
|
|
son = dad * 2 + 1;
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
void heap_sort(int arr[], int len)
|
|
|
{
|
|
|
int i; //初始化，i从最後一个父节点开始调整
|
|
|
for (i = len / 2 - 1; i >= 0; i--)
|
|
|
max_heapify(arr, i, len - 1); //先将第一个元素和已排好元素前一位做交换，再重新调整，直到排序完毕
|
|
|
for (i = len - 1; i > 0; i--)
|
|
|
{
|
|
|
swap(&arr[0], &arr[i]);
|
|
|
max_heapify(arr, 0, i - 1);
|
|
|
}
|
|
|
}
|
|
|
int main() {
|
|
|
int arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 };
|
|
|
int len = (int) sizeof(arr) / sizeof(*arr);
|
|
|
heap_sort(arr, len);
|
|
|
int i;
|
|
|
for (i = 0; i < len; i++)
|
|
|
printf("%d ", arr[i]);
|
|
|
printf("\n");
|
|
|
return 0;
|
|
|
}
|
|
|
3.4 运行时间结果
|
|
|
0 0 0 1 1 1 2 2 2 3 3 3 4 4 4 5 5 5 6 6 6 7 7 7 8 8 8 9 9 9
|
|
|
--------------------------------
|
|
|
Process exited after 0.01928 seconds with return value 0
|
|
|
请按任意键继续. . .
|
|
|
|
|
|
四、二路排序（这个一般是二路归并排序，在这里写归并排序）。
|
|
|
4.1 基本思想
|
|
|
将序列每相邻两个数字进行归并操作，形成floor(n / 2)个序列，排序后每个序列包含两个元素。将上述序列再次归并，形成floor(n / 4)个序列，每个序列包含四个元素.重复步骤2，直到所有元素排序完毕
|
|
|
4.2 复杂程度
|
|
|
归并排序是稳定的，它的最差，平均，最好时间都是O(nlogn)。但是它需要额外的存储空间.
|
|
|
4.3 程序
|
|
|
#include <stdio.h>
|
|
|
#include <stdlib.h>
|
|
|
#define N 7
|
|
|
void merge(int arr[], int low, int mid, int high){
|
|
|
int i, k;
|
|
|
int *tmp = (int *)malloc((high-low+1)*sizeof(int)); //申请空间，使其大小为两个
|
|
|
int left_low = low;
|
|
|
int left_high = mid;
|
|
|
int right_low = mid + 1;
|
|
|
int right_high = high;
|
|
|
for(k=0; left_low<=left_high && right_low<=right_high; k++){ // 比较两个指针所指向的元素
|
|
|
if(arr[left_low]<=arr[right_low]){
|
|
|
tmp[k] = arr[left_low++];
|
|
|
}else{
|
|
|
tmp[k] = arr[right_low++];
|
|
|
}
|
|
|
}
|
|
|
if(left_low <= left_high){ //若第一个序列有剩余，直接复制出来粘到合并序列尾
|
|
|
//memcpy(tmp+k, arr+left_low, (left_high-left_low+l)*sizeof(int));
|
|
|
for(i=left_low;i<=left_high;i++)
|
|
|
tmp[k++] = arr[i];
|
|
|
}
|
|
|
|
|
|
if(right_low <= right_high){
|
|
|
//若第二个序列有剩余，直接复制出来粘到合并序列尾
|
|
|
//memcpy(tmp+k, arr+right_low, (right_high-right_low+1)*sizeof(int));
|
|
|
for(i=right_low; i<=right_high; i++)
|
|
|
tmp[k++] = arr[i];
|
|
|
}
|
|
|
for(i=0; i<high-low+1; i++)
|
|
|
arr[low+i] = tmp[i];
|
|
|
free(tmp);
|
|
|
return;
|
|
|
}
|
|
|
void merge_sort(int arr[], unsigned int first, unsigned int last){
|
|
|
int mid = 0;
|
|
|
if(first<last){
|
|
|
mid = (first+last)/2; /* 注意防止溢出 */
|
|
|
/*mid = first/2 + last/2;*/
|
|
|
//mid = (first & last) + ((first ^ last) >> 1);
|
|
|
merge_sort(arr, first, mid);
|
|
|
merge_sort(arr, mid+1,last);
|
|
|
merge(arr,first,mid,last);
|
|
|
}
|
|
|
return 0;
|
|
|
}
|
|
|
int main(){
|
|
|
int i;
|
|
|
int a[N]={32,12,56,78,76,45,36};
|
|
|
printf ("排序前 \n");
|
|
|
for(i=0;i<N;i++)
|
|
|
printf("%d\t",a[i]);
|
|
|
merge_sort(a,0,N-1); // 排序
|
|
|
printf ("\n 排序后 \n");
|
|
|
for(i=0;i<N;i++)
|
|
|
printf("%d\t",a[i]); printf("\n");
|
|
|
system("pause");
|
|
|
return 0;
|
|
|
}
|
|
|
4.4 运行时间结果：
|
|
|
排序前
|
|
|
32 12 56 78 76 45 36
|
|
|
排序后
|
|
|
12 32 36 45 56 76 78
|
|
|
请按任意键继续. . .
|
|
|
|
|
|
五、希尔排序
|
|
|
5.1 基本思想
|
|
|
希尔排序是特殊的插入排序，直接插入排序每次插入前的遍历步长为1，而希尔排序是将待排序列分为若干个子序列，对这些子序列分别进行直接插入排序，当每个子序列长度为1时，再进行一次直接插入排序时，结果一定是有序的。常见的划分子序列的方法有：初始步长（两个子序列相应元素相差的距离）为要排的数的一半，之后每执行一次步长折半。
|
|
|
5.2 复杂程度
|
|
|
在最优的情况下，希尔排序的时间复杂度为O(n1.3)，在最差的情况下，希尔排序的时间复杂度为：O(n2).
|
|
|
5.3 程序
|
|
|
#include <stdio.h>
|
|
|
int shsort(int s[], int n)//自定义函数 shsort()
|
|
|
{
|
|
|
int i,j,d;
|
|
|
d=n/2; //确定固定增虽值
|
|
|
while(d>=1)
|
|
|
{
|
|
|
for(i=d+1;i<=n;i++)
|
|
|
//数组下标从d+1开始进行直接插入排序
|
|
|
{
|
|
|
s[0]=s[i]; //设置监视哨
|
|
|
j=i-d;
|
|
|
//确定要进行比较的元素的最右边位置
|
|
|
while((j>0)&&(s[0]<s[j]))
|
|
|
{
|
|
|
s[j+d]=s[j];//数据右移
|
|
|
j=j-d;//向左移d个位置/
|
|
|
}
|
|
|
s[j + d]=s[0];
|
|
|
//在确定的位罝插入s[i]
|
|
|
}
|
|
|
d = d/2; //增里变为原来的一半
|
|
|
}
|
|
|
return 0;
|
|
|
}
|
|
|
int main()
|
|
|
{
|
|
|
int a[11],i;
|
|
|
//定义数组及变量为基本整型
|
|
|
printf("请输入 10 个数据：\n");
|
|
|
for(i=1;i<=10;i++)
|
|
|
scanf("%d",&a[i]);
|
|
|
//从键盘中输入10个数据
|
|
|
shsort(a, 10);
|
|
|
//调用 shsort()函数
|
|
|
printf("排序后的顺序是：\n");
|
|
|
for(i=1;i<=10;i++)
|
|
|
printf("%5d",a[i]);
|
|
|
//输出排序后的数组
|
|
|
printf("\n");
|
|
|
return 0;
|
|
|
}
|
|
|
5.4 运行时间结果
|
|
|
请输入 10个数据:
|
|
|
6 98 3 25 66 78 51 20 93 64
|
|
|
排序后的顺序是:
|
|
|
3 20 25 51 56 64 66 78 93 98
|
|
|
rocess exited after 20.85 seconds with return value 0
|
|
|
请按任意键继续.
|
|
|
|
|
|
六、直接插入法排序
|
|
|
6.1 基本思想
|
|
|
插入排序算法 是所有排序方法中最简单的一种算法，其主要的实现思想是将数据按照一定的顺序一个一个的插入到有序的表中，最终得到的序列就是已经排序好的数据。直接插入排序 是插入排序算法中的一种， 采用的方法是：在添加新的记录时，使用 顺序查找 的方式找到其要插入的位置，然后将新记录插入。
|
|
|
6.2 复杂程度
|
|
|
最坏情况：O(N^2)
|
|
|
最好情况：O(N^2)
|
|
|
平均情况：O(N^2)
|
|
|
6.3 程序：
|
|
|
1.每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。
|
|
|
2.第一趟比较前两个数，然后把第二个数按大小插入到有序表中；
|
|
|
3.第二趟把第三个数据与前两个数从后向前扫描，把第三个数按大小插入到有序表中；
|
|
|
4.依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程。
|
|
|
#include <stdio.h>
|
|
|
int insort(int s[], int n) /* 自定义函数 insort()*/
|
|
|
{
|
|
|
int i,j;
|
|
|
for(i=2;i<=n;i++) //数组下标从2开始，s[0]做监视哨，s[1]一个数据无可比性
|
|
|
{
|
|
|
s[0]=s[i]; //给监视哨陚值
|
|
|
j=i-1; //确定要比较元素的最右边位黄
|
|
|
while(s[0]<s[j])
|
|
|
{
|
|
|
s[j+1]=s[j]; //数据右移
|
|
|
j--; //产移向左边一个未比较的数
|
|
|
}
|
|
|
s[j+1]=s[0]; //在确定的位置插入s[i]
|
|
|
}
|
|
|
return 0;
|
|
|
}
|
|
|
int main()
|
|
|
{
|
|
|
int a[11],i; //定义数组及变量为基木整甩
|
|
|
printf("请输入10个数据：\n");
|
|
|
for (i =1;i<=10;i++)
|
|
|
scanf("%d",&a[i]); //接收从键盘输入的10个数据到数组a中
|
|
|
printf("原始顺序：\n");
|
|
|
for(i=1;i<11;i++)
|
|
|
printf("%5d",a[i]); //将未排序前的顺序输出
|
|
|
insort(a,10); //调用自定义函数 insort()
|
|
|
printf("\n 插入数据排序后顺序：\n");
|
|
|
for(i=1;i<11;i++)
|
|
|
printf("%5d",a[i]); //将排序后的数组输出
|
|
|
printf("\n");
|
|
|
return 0;
|
|
|
}
|
|
|
6.4 运行时间结果
|
|
|
请输入10个数据:
|
|
|
25 12 65 53 46 89 52 11 20 96
|
|
|
原始顺序:
|
|
|
25 12 65 53 46 89 52 11 20 96
|
|
|
插入数据排序后顺序:
|
|
|
11 12 20 25 46 52 53 65 89 96
|
|
|
Process exited after 19.24 seconds with return value 0
|
|
|
请按任意键继续.
|
|
|
|
|
|
七、计数排序
|
|
|
7.1 描述
|
|
|
计数排序的基本思想是对于给定的输入序列中的每一个元素x，确定该序列中值小于x的元素的个数（此处并非比较各元素的大小，而是通过对元素值的计数和计数值的累加来确定）。一旦有了这个信息，就可以将x直接存放到最终的输出序列的正确位置上。例如，如果输入序列中只有17个元素的值小于x的值，则x可以直接存放在输出序列的第18个位置上。
|
|
|
7.2 复杂程度
|
|
|
时间复杂度：O(n+k)
|
|
|
空间复杂度：O(n+k)
|
|
|
7.3 代码
|
|
|
#include<stdio.h>
|
|
|
#include<stdlib.h>
|
|
|
#include<string.h>
|
|
|
#include<time.h>
|
|
|
void csort(int *src,int *dst,int size,int k)
|
|
|
{
|
|
|
int i;
|
|
|
int *count = malloc(size*sizeof(int));
|
|
|
for(i=0;i<k;i++)
|
|
|
{
|
|
|
count[i] = 0;
|
|
|
}
|
|
|
for(i=0;i<size;i++)
|
|
|
{
|
|
|
|
|
|
count[src[i]]++;
|
|
|
}
|
|
|
for(i=1;i<k;i++)
|
|
|
{
|
|
|
|
|
|
count[i] += count[i-1];
|
|
|
}
|
|
|
for(i=0;i<size;i++)
|
|
|
{
|
|
|
|
|
|
dst[--count[src[i]]]= src[i];
|
|
|
}
|
|
|
}
|
|
|
int main(int argc,char **argv)
|
|
|
{
|
|
|
int *src = NULL,*dst = NULL;
|
|
|
int size = 100;
|
|
|
int i,k;
|
|
|
src = malloc(size * sizeof(int));
|
|
|
dst = malloc(size * sizeof(int));
|
|
|
srand(time(0));
|
|
|
for(i=0;i<size;i++)
|
|
|
{
|
|
|
src[i] = rand() % 100;
|
|
|
}
|
|
|
k = 100;
|
|
|
csort(src,dst,size,k);
|
|
|
printf("src:");
|
|
|
for(i=0;i<size;i++)
|
|
|
{
|
|
|
printf(" %d",src[i]);
|
|
|
}
|
|
|
printf(".\n");
|
|
|
printf("dst:");
|
|
|
for(i=0;i<size;i++)
|
|
|
{
|
|
|
printf(" %d",dst[i]);
|
|
|
}
|
|
|
printf(".\n");
|
|
|
}
|
|
|
7.4 运行时间结果
|
|
|
运行时间：0.17s
|
|
|
运行结果：
|
|
|
排序前：46 95 25 92 68 64 20 9 26 60 80 3 12 48 62 64 66 23 59 59 70 3 46 17 85 1 5 17 30 97 39 77 50 23 10 27 93 60 98 70 83 47 6 64 86 29 69 87 27 71 36 51 83 40 46 40 72 42 67 53 45 33 22 0 50 17 84 14 19 3 10 73 82 35 71 92 19 24 57 39 4 5 46 48 77 99 80 49 2 35 45 31 15 5 8 50 91 9 20 38.
|
|
|
排序后： 0 1 2 3 3 3 4 5 5 5 6 8 9 9 10 10 12 14 15 17 17 17 19 19 20 20 22 23 23 24 25 26 27 27 29 30 31 33 35 35 36 38 39 39 40 40 42 45 45 46 46 46 46 47 48 48 49 50 50 50 51 53 57 59 59 60 60 62 64 64 64 66 67 68 69 70 70 71 71 72 73 77 77 80 80 82 83 83 84 85 86 87 91 92 92 93 95 97 98 99.
|
|
|
|
|
|
八、选择排序
|
|
|
8.1 描述
|
|
|
选择排序是一种简单直观的排序算法，以从小到大排序为例，它在未排序序列中找到最小的元素，将其存放在排序序列起始的位置，从剩余未排序元素中继续寻找最小的元素放在已排序序列末尾，以此类推，直到所有元素均排序完毕。
|
|
|
8.2 复杂程度
|
|
|
时间复杂度：O(n^2)
|
|
|
空间复杂度：O(1)
|
|
|
8.3 代码
|
|
|
#include<stdio.h>
|
|
|
void solve(int a[],int n)
|
|
|
{
|
|
|
int i,j,t;
|
|
|
for(i=0;i<n;i++)
|
|
|
{
|
|
|
for(j=i+1;j<n;j++)
|
|
|
{
|
|
|
if(a[i]>a[j])
|
|
|
{
|
|
|
t=a[i];
|
|
|
a[i]=a[j];
|
|
|
a[j]=t;
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
int main()
|
|
|
{
|
|
|
int a[100],n,i;
|
|
|
scanf("%d",&n);
|
|
|
for(i=0;i<n;i++)
|
|
|
{
|
|
|
scanf("%d",&a[i]);
|
|
|
}
|
|
|
solve(a,n);
|
|
|
for(i=0;i<n;i++)
|
|
|
{
|
|
|
printf("%d ",a[i]);
|
|
|
}
|
|
|
return 0;
|
|
|
}
|
|
|
9.4运行时间：0.17s
|
|
|
运行结果：输入：10
|
|
|
5 7 6 4 2 1 8 9 3 16
|
|
|
输出：1 2 3 4 5 6 7 8 9 16
|
|
|
|
|
|
九、带哨兵直接插入排序法
|
|
|
9.1 描述
|
|
|
带哨兵直接插入法排序分为有序区和无序区，初次，将第一个元素作为有序区，将无序区第一个元素作为哨兵，插入到有序区合适的位置，从而得到一个新的有序区，依次类推直到全部插入完成。
|
|
|
9.2 复杂程度
|
|
|
最好的情况，时间复杂度：O(n)
|
|
|
最差的情况，时间复杂度：O(n^2)
|
|
|
9.3 代码
|
|
|
#include<stdio.h>
|
|
|
#include<stdlib.h>
|
|
|
int a[11]={0,3,78,67,45,90,34,6,35,90,98};
|
|
|
void InSertSort(int a[],int length)
|
|
|
{
|
|
|
int i,j;
|
|
|
for(i=2;i<length;i++)
|
|
|
{
|
|
|
a[0]=a[i];
|
|
|
for(j=i-1;a[j]>a[0];j--)
|
|
|
{
|
|
|
a[j+1]=a[j];
|
|
|
}
|
|
|
a[j+1]=a[0];
|
|
|
}
|
|
|
}
|
|
|
void Print(int a[],int length)
|
|
|
{
|
|
|
int i;
|
|
|
for(i=0;i<length;i++)
|
|
|
{
|
|
|
printf(" %d",a[i]);
|
|
|
}
|
|
|
}
|
|
|
int main()
|
|
|
{
|
|
|
|
|
|
printf("插入前数列：");
|
|
|
Print(a,11);
|
|
|
printf("\n");
|
|
|
printf("插入后数列：");
|
|
|
InSertSort(a,11);
|
|
|
Print(a,11);
|
|
|
printf("\n");
|
|
|
system("pause");
|
|
|
return 0;
|
|
|
}
|
|
|
9.4 运行时间结果
|
|
|
运行时间：0.16s
|
|
|
运行结果：插入前数列： 0 3 78 67 45 90 34 6 35 90 98
|
|
|
插入后数列： 98 3 6 34 35 45 67 78 90 90 98
|
|
|
请按任意键继续. . .
|
|
|
|
|
|
十、基数排序
|
|
|
10.1 算法思想
|
|
|
基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。
|
|
|
有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。
|
|
|
10.2 复杂程度
|
|
|
基数排序的时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数
|
|
|
注：比其他的稳定
|
|
|
10.3 程序
|
|
|
#include<stdio.h>
|
|
|
void radixSort(int *a,int size)
|
|
|
{
|
|
|
int temp[10][20]={0}; //第一个10表示0~9，第二个20表示a的size
|
|
|
int order[10]={0};
|
|
|
int i,j,k; //k表示当前比较的那一位上的具体数字
|
|
|
int n; //n=1,10,100,1000...取决于a中的最大的数
|
|
|
int p;
|
|
|
n=1;
|
|
|
while(n <= 100)
|
|
|
{
|
|
|
for(i=0;i<size;i++)
|
|
|
{
|
|
|
k = (a[i]/n) % 10;
|
|
|
temp[k][order[k]] = a[i];
|
|
|
order[k]++;
|
|
|
}
|
|
|
p=0; //p为一次排序过程中,a的脚标
|
|
|
for(i=0;i<10;i++)
|
|
|
{
|
|
|
if(order[i] != 0)
|
|
|
{
|
|
|
for(j=0;j<order[i];j++)
|
|
|
{
|
|
|
a[p] = temp[i][j];
|
|
|
p++;
|
|
|
}
|
|
|
order[i] = 0;
|
|
|
}
|
|
|
}
|
|
|
n *= 10;
|
|
|
}
|
|
|
}
|
|
|
int main()
|
|
|
{
|
|
|
int a[20]={3,22,93,3,5,14,28,65,39,81,71,72,48,39,55,105,129,184,196,208};
|
|
|
int i;
|
|
|
radixSort(a,20);
|
|
|
for(i=0;i<20;i++)
|
|
|
printf("%d ",a[i]);
|
|
|
}
|
|
|
10.4 运行时间结果
|
|
|
65 93 105 196 208
|
|
|
Pr9sees.exitee after 0.04504 seconds with return value O
|
|
|
请按任意键继续.
|
|
|
|
|
|
十一、二分插入排序
|
|
|
11.1 算法思想
|
|
|
二分插入排序的基本思想和插入排序一致；都是将某个元素插入到已经有序的序列的正确的位置；和直接插入排序的最大区别是，元素A[i]的位置的方法不一样；直接插入排序是从A[i-1]往前一个个比较，从而找到正确的位置；而二分插入排序，利用前i-1个元素已经是有序的特点结合二分查找的特点，找到正确的位置，从而将A[i]插入，并保持新的序列依旧有序；
|
|
|
11.2 复杂程度
|
|
|
时间复杂度：
|
|
|
T(n) = O(n);
|
|
|
11.3 程序
|
|
|
void insertSortBinary( int num[], int count )
|
|
|
{
|
|
|
int i, j;
|
|
|
for( i = 1; i < count; i++ )
|
|
|
{
|
|
|
if( num[i] < num[i - 1] )
|
|
|
{
|
|
|
int temp = num[i];
|
|
|
int left = 0, right = i - 1;
|
|
|
while( left <= right )
|
|
|
{
|
|
|
int mid = ( left + right ) / 2;
|
|
|
if( num[mid] < temp )
|
|
|
{
|
|
|
left = mid + 1;
|
|
|
}
|
|
|
else
|
|
|
{
|
|
|
right = mid - 1;
|
|
|
}
|
|
|
}
|
|
|
//只是比较次数变少了，交换次数还是一样的
|
|
|
for( j = i; j > left; j-- )
|
|
|
{
|
|
|
num[j] = num[j - 1];
|
|
|
}
|
|
|
num[left] = temp;
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
11.4 运行时间结果
|
|
|
下面在测试一下随机生成10000个数据排序需要的次数和时间
|
|
|
insertSortBinary test共执行了9891次!执行时间为129ms
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
