首页 > 代码库 > 数据结构与算法 4:排序算法,选择/插入/冒泡/希尔/快速/归并
数据结构与算法 4:排序算法,选择/插入/冒泡/希尔/快速/归并
【本文谢绝转载，原文来自http://990487026.blog.51cto.com】
排序算法 平均复杂度
冒泡排序 O(n2)
选择排序 O(n2)
插入排序 O(n2)
希尔排序 O(n1.5)
快速排序 O(N*logN)
归并排序 O(N*logN)
堆排序 O(N*logN)
基数排序 O(d(n+r))
选择排序:
chunli@http://990487026.blog.51cto.com~/sort$ cat main.c
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
void printArray01(int array[], int len)
{
int i = 0;
for(i=0; i<len; i++)
{
printf("%d ", array[i]);
}
printf("\n");
}
void swap01(int array[], int i, int j)
{
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
void SelectionSort(int array[], int len) // O(n*n)
{
int i = 0;
int j = 0;
int k = -1;
for(i=0; i<len; i++)
{
k = i; //寻找最小元素的下标
for(j=i+1; j<len; j++)
{
if( array[j] < array[k] ) //开始寻找最小元素的下标
{
k = j;
}
}
swap01(array, i, k);
}
}
int main()
{
int array[] = {12, 5, 433, 253, 216, 7};
int len = sizeof(array) / sizeof(*array);
printArray01(array, len);
SelectionSort(array, len);
printArray01(array, len);
return 0;
}
chunli@http://990487026.blog.51cto.com~/sort$ gcc main.c -Wall && ./a.out
12 5 433 253 216 7
5 7 12 216 253 433
chunli@http://990487026.blog.51cto.com~/sort$插入法排序:
chunli@http://990487026.blog.51cto.com~/sort$ cat main.c
#include <stdio.h>
void insert_sort(int *arr,int len)//时间复杂度 O^2
{
int i = 0;
int j = 0;
int k = 0;
int t = -1;
for(i=1;i<len;i++)
{
k=i;//待插入位置
t=arr[k];
for(j=i-1;(j>=0 && (arr[j]>t));j--)
{
arr[j+1] =arr[j];//元素往后移动
k = j; //k 需要插入的位置
}
arr[k] = t; //元素插入
}
}
void print_arr(int *arr,int len)
{
int i = 0;
for(i=0;i<len;i++)
{
printf("%d ",*(arr+i));
}
printf("\n");
}
int main()
{
int arr[] = {12,55,66,11,22,1,99,2,7};
print_arr(arr,sizeof(arr)/sizeof(int));
insert_sort(arr,sizeof(arr)/sizeof(int));
print_arr(arr,sizeof(arr)/sizeof(int));
return 0;
}
chunli@http://990487026.blog.51cto.com~/sort$ gcc main.c -Wall && ./a.out
12 55 66 11 22 1 99 2 7
1 2 7 11 12 22 55 66 99
chunli@http://990487026.blog.51cto.com~/sort$冒泡排序(增强版):相邻元素比较
chunli@http://990487026.blog.51cto.com~/sort$ cat main.c
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
void printfArray03(int array[], int len)
{
int i = 0;
for(i=0; i<len; i++)
{
printf("%d ", array[i]);
}
printf("\n");
}
void swap03(int array[], int i, int j)
{
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
void BubbleSort(int array[], int len) // O^2
{
int i = 0;
int j = 0;
int exchange = 1; //表明数组是否已经排好序 已经排好序为0 1表示没有排好序
for(i=0; (i<len) && exchange; i++)//只要完全排好了,就直接跳出来
{
exchange = 0;//认为已经排序完毕的标签，如果在内部没有改变状态则认为已经排序完成。
for(j=len-1; j>i; j--)
{
if( array[j] < array[j-1] )
{
swap03(array, j, j-1);
exchange = 1;//
}
}
}
}
int main()
{
int array[] ={8,3,6,1,222,4,778,963,12,45,7,8};
int len = sizeof(array) / sizeof(*array);
printfArray03(array, len);
BubbleSort(array, len);
printfArray03(array, len);
return 0;
}
chunli@http://990487026.blog.51cto.com~/sort$ gcc main.c -Wall && ./a.out
8 3 6 1 222 4 778 963 12 45 7 8
1 3 4 6 7 8 8 12 45 222 778 963
chunli@http://990487026.blog.51cto.com~/sort$希尔排序(分组技术)
chunli@http://990487026.blog.51cto.com~/sort$ cat main.c
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
void println(int array[], int len)
{
int i = 0;
for(i=0; i<len; i++)
{
printf("%d ", array[i]);
}
printf("\n");
}
void swap(int array[], int i, int j)
{
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
void InertionSort_ddddd(int array[], int len) // O(n*n)
{
int i = 0;
int j = 0;
int k = -1;
int temp = -1;
//{12, 5, 433, 253, 216, 7};
for(i=1; i<len; i++)
{
k = i; //待插入位置
temp = array[k];
for(j=i-1; (j>=0) && (array[j]>temp); j--)
{
array[j+1] = array[j]; //元素后移
k = j; //k需要插入的位置
}
array[k] = temp;//元素插入
}
}
//nlogn
void ShellSort(int array[], int len) //
{
int i = 0;
int j = 0;
int k = -1;
int temp = -1;
int gap = len;
do
{
//业界统一实验的 平均最好情况 经过若干次后，收敛为1
gap = gap / 3 + 1; //gap /2345 2000 都行 //O（n 1.3）
for(i=gap; i<len; i+=gap)
{
k = i;
temp = array[k];
for(j=i-gap; (j>=0) && (array[j]>temp); j-=gap)
{
array[j+gap] = array[j];
k = j;
}
array[k] = temp;
}
}while( gap > 1 );
}
int main()
{
int array[] = {12, 5, 433, 253, 216, 7,12,4,6,76,88,12,13,4,6};
int len = sizeof(array) / sizeof(*array);
println(array, len);
ShellSort(array, len);
println(array, len);
return 0;
}
chunli@http://990487026.blog.51cto.com~/sort$ gcc main.c -Wall && ./a.out
12 5 433 253 216 7 12 4 6 76 88 12 13 4 6
4 4 5 6 6 7 12 12 12 13 76 88 216 253 433
chunli@http://990487026.blog.51cto.com~/sort$快速排序(递归)
chunli@http://990487026.blog.51cto.com~/sort$ cat main.c
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
void printArray(int array[], int len)
{
int i = 0;
for(i=0; i<len; i++)
{
printf("%d ", array[i]);
}
printf("\n");
}
void swap5(int array[], int i, int j)
{
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
//划分过程 第一个元素当枢轴，分成2个有效子序列
int partition(int array[], int low, int high)
{
int pv = array[low];
while( low < high )
{
while( (low < high) && (array[high] >= pv) )
{
high--; //比基准大，本来就在右边，所以high前移动
}
swap5(array, low, high);
while( (low < high) && (array[low] <= pv) )
{
low++;
}
swap5(array, low, high);
}
//返回枢轴的位置。。。重要
return low;
}
//让n个元素 依此减少 减少到1个元素的时候，因为1个元素可以看成一个有序的序列
void QSort2(int array[], int low, int high)
{
if( low < high )
{
int pivot = partition(array, low, high);
//对子序列1排序
QSort2(array, low, pivot-1);
//对子序列2排序
QSort2(array, pivot+1, high);
}
}
void QSort(int array[], int low, int high)
{
if( low < high )
{
int pivot = partition(array, low, high);
//对子序列1排序
QSort2(array, low, pivot-1);
//对子序列2排序
QSort2(array, pivot+1, high);
}
}
void QuickSort(int array[], int len) // O(n*logn)
{
QSort(array, 0, len-1);
}
int main()
{
int array[] = {12, 5, 433, 253, 216, 7};
//int array[] = {12, 5};
int len = sizeof(array) / sizeof(*array);
printArray(array, len);
QuickSort(array, len);
printArray(array, len);
return 0;
}
chunli@http://990487026.blog.51cto.com~/sort$ gcc main.c -Wall && ./a.out
12 5 433 253 216 7
5 7 12 216 253 433
chunli@http://990487026.blog.51cto.com~/sort$归并排序:
chunli@http://990487026.blog.51cto.com~/sort$ cat main.c
#include <stdio.h>
#include <malloc.h>
void printArray06(int array[], int len)
{
int i = 0;
for(i=0; i<len; i++)
{
printf("%d ", array[i]);
}
printf("\n");
}
void swap6(int array[], int i, int j)
{
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
void Merge(int src[], int des[], int low, int mid, int high)
{
int i = low;
int j = mid + 1;
int k = low;
while( (i <= mid) && (j <= high) ) //将小的放到目的地中
{
if( src[i] < src[j] )
{
des[k++] = src[i++];
}
else
{
des[k++] = src[j++];
}
}
while( i <= mid ) //若还剩几个尾部元素
{
des[k++] = src[i++];
}
while( j <= high ) //若还剩几个尾部元素
{
des[k++] = src[j++];
}
}
//每次分为两路 当只剩下一个元素时，就不需要在划分
void MSort(int src[], int des[], int low, int high, int max)
{
if( low == high ) //只有一个元素，不需要归并，结果赋给des[low]
{
des[low] = src[low];
}
else //如果多个元素，进行两路划分
{
int mid = (low + high) / 2;
int* space = (int*)malloc(sizeof(int) * max);
//递归进行两路，两路的划分
//当剩下一个元素的时，递归划分结束，然后开始merge归并操作
if( space != NULL )
{
MSort(src, space, low, mid, max);
MSort(src, space, mid+1, high, max);
Merge(space, des, low, mid, high); //调用归并函数进行归并
}
free(space);
}
}
void MergeSort(int array[], int len) // O(n*logn)
{
MSort(array, array, 0, len-1, len);
}
int main()
{
int array[] = {21, 25, 49, 25, 16, 8};
int len = sizeof(array) / sizeof(*array);
printArray06(array, len);
MergeSort(array, len);
printArray06(array, len);
return 0;
}
chunli@http://990487026.blog.51cto.com~/sort$ gcc main.c -Wall && ./a.out
21 25 49 25 16 8
8 16 21 25 25 49
chunli@http://990487026.blog.51cto.com~/sort$【本文谢绝转载，原文来自http://990487026.blog.51cto.com】
本文出自 “魂斗罗” 博客，谢绝转载！
数据结构与算法 4:排序算法,选择/插入/冒泡/希尔/快速/归并
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。