根据不同的设计思想可以把算法分为多种，常见的又插入类、交换类和选择类三种。
（1）插入类排序
插入类排序是指在一个已经排好序的序列中插入一个新元素，也就是从一个未排序的无序序列中取出一个元素，然后插入到已经排好序的序列中，直到所有的元素都插入完成，就得到了一个新的有序序列，常见的插入排序算法有：直接插入排序。
在插入排序中，需要将取出的数据与其左边的数字继续比较。如果左边的数字小，就不需要继续比较，本轮操作到此结束，自然也不需要交换数字的位置，然而，如果取出的数字比左边已归位的数字都要小，就必须不停的比较大小，交换数字，直到它达到整个序列的最左边为止。具体来说，就是第K轮需要比较k-1次(因为自己不需要跟自己比较)。因此，在最糟糕的情况下，第二轮需要操作1次，第三轮操作2次…..第n轮需要操作n-1次，所以插入排序的最坏时间复杂度为O(n2)，也就是当序列的元素是按照从大到小输入的情况，所以直接插入排序算法适合序列基本有序的情景
插入排序就是一种简单快速的排序算法，把一组无序的数据，以第一个数据为准，假设第一个数据是经过排序过的，把第二个数据和排号的数据继续比较，注意插入排序是从后向前进行比较，如果此时有一个新元素，则从已经排序的序列尾部向前进行比较，如果排序过的序列的元素值大于新元素，则把新元素插入到该元素的前面。
插入排序的思路就是从右侧的未排序区域内取出一个数据，然后将它插入到已排序区域内合适的位置上
#include <stdio.h>
void InsertSort(int *arr,int size)
{
//存储待插入元素的值
int temp=0;
//定义一个变量存储需要移动的元素
int num=0;
//循环从无序中的拿出元素
for(int i=1;i<size;i++){
//备份待插入的值
temp = arr[i];
//循环从无序队列中拿出的值与有序队列中每个数进行比较
for(int j=i-1;j>=0;j--){
//如果插入元素比有序数小
if(temp < arr[j]){
//备份有序数列当前的下标
num = j;
//将比待插入的大的往后移
arr[j+1]=arr[j];
}else{
//如果待插入数字比有序数字大，保留当前插入动作，并退出
num = j+1;
break;
}
}
//将待插入数字插入到合适位置
arr[num] = temp;
}
for(int n=0;n<size;n++){
printf("arr[%d] = %d,",n,arr[n]);
}
printf("\n");
}
int main(){
int arr[]={7,9,8,5,6,2};
printf("排序前：");
for(int i=0;i<5;i++){
printf("arr[%d] = %d ,",i,arr[i]);
}
printf("\n");
printf("排序后：");
InsertSort(arr,sizeof(arr)/sizeof(arr[0]));
}
效果如下：
（2）交换类排序
交换类排序算法的核心是“交换”，也就是每一轮排序都是通过一系列交换动作实现的，最终让元素排列到合适的位置上。常见的交换类排序算法有：冒泡排序、快速排序
冒泡排序：
冒泡排序也被称为起泡排序，该排序算法的原理就是经过一系列的交换实现的，也就是用第一个元素和第二个元素进行比较，如果第一个元素的值和大于第二个元素则两者位置互换，否则不交换。然后第二个元素和第三个元素交换比较…..最后序列中最大的元素被交换到了序列的尾部，这样就完成了一轮交换，经过n轮交换之后，就可以得到一个有序序列。
除了从左向右交换的方案，还可以从右向左开始比较相邻两个数字的大小，再根据结果交换两个数字的“位置”这一操作的算法，在这个过程中，数字会向泡泡一样，慢慢从右往左“浮”到序列的顶端，所以这个算法才被称为“冒泡排序”
在冒泡排序中，第1轮需要比较n-1次，第二轮需要比较n-2次…..第n-1轮需要比较1.因此总的比较次数为(n-1)+(n-2)+…+1≈n2/2。这个比较次数恒定为该数值，和输入数据的排列顺序无关。
不过，交换数字的次数和输入数据的排列顺序有关。假设出现某种极端情况，如输入数据正好以小到大的顺序排序，那么便不需要任何交换操作：反过来，输入数据要以从大到小的顺序排列，那么每次比较数字后都要进行交换。因此，冒泡排序的时间复杂度为O(n2).
注：设计冒泡排序算法的时候排序结束的条件应该是一轮排序过程中没有发生元素交换。
#include <stdio.h>
void BubbleSort(int *arr,int size)
{
int temp=0;
//数组中有几个数，就需要遍历几个数-1次
for(int i=0;i<size-1;i++){
//每个数需要判断的次数
for(int j=0;j<size-i;j++){
if(arr[j]>arr[j+1]){
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
for(int i=0;i<size;i++){
printf("arr[%d] = %d ",i,arr[i]);
}
printf("\n");
}
int main(int argc,char const* argv[])
{
int arr[]={5,9,4,6,1};
printf("未排序前：");
for(int i=0;i<5;i++){
printf("arr[%d] = %d ",i,arr[i]);
}
printf("\n");
printf("未排序后：");
BubbleSort(arr,sizeof(arr)/sizeof(arr[0]));
return 0;
}
效果如下：
选择排序：
选择排序的主要动作就是“选择”，排序原理其实就是从未排序的梳理找到最小的元素，放在已排序数列的开始位置，然后再从未排序的数列找到最小的元素，然后再放置已排序数列的末尾。
选择排序就是重复“从待排序的数据中寻找最小值，将其与序列最左边的数字进行交换”。
#include <stdio.h>
void SelectSort(int *arr,int size)
{
//定义一变量存储最小值
int min=0;
//再定义一个变量存储需要交换的下标
int temp=0;
//数组中有多少个元素，就要执行元素-1次
for(int i=0;i<size-1;i++){
//假设未排序后的数组中第一个最小值
min = arr[i];
//寻找找到最小值
for(int j=i+1;j<size;j++){
if(min > arr[j]){
min = arr[j];
temp = j;
}
}
//交换乱序中一个假设最小的值
arr[temp] = arr[i];
arr[i] = min;
}
//遍历排序后的数组
for(int i=0;i<size;i++){
printf("arr[%d] = %d ",i,arr[i]);
}
printf("\n");
}
int main(int argc,char const* argv[])
{
int arr[]={5,7,4,9,3};
printf("排序前的数组：");
for(int i=0;i<5;i++){
printf("arr[%d] = %d ",i,arr[i]);
}
printf("\n");
printf("排序前的数组：");
SelectSort(arr,sizeof(arr)/sizeof(arr[0]));
return 0;
}
效果如下:
快速排序：
快速排序也属于交换类的排序算法，特点是通过多次划分操作实现排序。快速排序算法首先会在序列中随机选择一个基准值（通常是序列中第一个元素），然后将除了基准值以外的数分为“比基准值小的数”和“比基准值大的数”这两个类别，再将其排列成以下形式。
[ 比基准值小的数 ] 基准值 [ 比基准值大的数 ]
接着对两个“[]”中的数据进行排序之后，整体的排序便完成了。对“[]”里面的数据进行排序时同样也会使用快速排序。
快速排序是一种“分治法”。他将原本的问题分成两个子问题（比基准值小的数和比基准值大的数），然后再分别解决这两个问题。子问题就是子序列完成排序后，再把他们合并成一个序列，那么对原始序列的排序也就完成了。
不过，解决子问题的时候会再次快速排序，甚至在这个快速排序里仍然要使用快速排序。只有在子问题里只剩一个数字的时候，排序才算完成。快速排序的算法中可以体现出“递归”。
当要排序的序列越无序，快速排序算法的效率越高，当要排序的序列越有序，该算法的效率越低。
二分查找的时间复杂度为O(logn)，与线性查找的O(n)相比速度上得到了指数倍提高，也就是x=log2n,则n=2x。
发表回复