排序算法——选择,插入,冒泡,希尔,快排,归并
程序员文章站
2022-06-04 15:08:19
...
1.选择排序
思想:从所有待排元素中选择最小元素
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);
}
}
2.插入排序
插入排序就是整理扑克。
思想:(1)空出空位(2)移动位置,找到插入位置
void InertionSort(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;//元素插入
}
}
3.冒泡排序
思想:相邻元素比较,符合条件就交换
冒泡改进,加了exchange,如果已经排好序了,就不需要执行完全部操作。
void BubbleSort(int array[], int len) // O(n*n)
{
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;//
}
}
}
}
4.希尔排序
思想:插入排序+分组
特点:效率突破n*n,但是由于分组,所以不稳定。
//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++) //通过 i++,实现对所有组进行插入排序
{
if(array[i - gap] < array[i])
continue;
k = i;
temp = array[k];
for(j=i-gap; (j>=0) && (array[j]>t
{
array[j+gap] = array[j];
k = j;
}
array[k] = temp;
}
}while( gap > 1 );
}
5.快速排序
思想:递归+找中
特点:(1)突破n*n(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;
}
void QSort(int array[], int low, int high)
{
if( low < high )
{
int pivot = partition(array, low, high);
//对子序列1排序
QSort(array, low, pivot-1);
//对子序列2排序
QSort(array, pivot+1, high);
}
}
void QuickSort(int array[], int len) // O(n*logn)
{
QSort(array, 0, len-1);
}
6.归并排序
思想:(1)将无序序列变成单元素序列(有序序列)(2)两个有序序列合并成一个有序序列
特点:(1)突破n*n(2)稳定(3)以空间换时间
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);
}
算法总结:
推荐阅读
-
Python实现的插入排序,冒泡排序,快速排序,选择排序算法示例
-
java 合并排序算法、冒泡排序算法、选择排序算法、插入排序算法、快速排序算法的描述
-
Java 排序算法整合(冒泡,快速,希尔,拓扑,归并)
-
java 基础排序(冒泡、插入、选择、快速)算法回顾
-
Python实现的插入排序,冒泡排序,快速排序,选择排序算法示例
-
python一些排序算法-冒泡,快排
-
PHP四种排序算法实现及效率分析【冒泡排序,插入排序,选择排序和快速排序】
-
C++学习(三十八)(C语言部分)之 排序(冒泡 选择 插入 快排)
-
C语言学习历程(十七)数据结构与排序(冒泡、选择、希尔排序)算法
-
选择排序、冒泡排序、插入排序、归并排序、快速排序的Java实现以及优化