目录
一、简单选择排序
二、冒泡排序
三、直接插入排序
四、希尔排序
五、快速排序
一、简单选择排序
简单选择排序（Simple Selection Sort）是一种简单直观的排序算法。它的基本思想是每一趟从待排序的数据元素中选择最小（或最大）的一个元素作为首元素，直到所有元素排完为止。
简单选择排序的具体步骤如下：
- 首先，在待排序序列中找到最小的元素，将其与第一个元素交换位置；
- 然后，在剩下的待排序序列中找到最小的元素，将其与第二个元素交换位置；
- 依次类推，直到整个序列排完为止。
简单选择排序的时间复杂度为O(n^2)，空间复杂度为O(1)。由于每一趟只进行一次交换，因此它的交换次数相对较少，适用于数据量较小时使用。但是，由于每一趟只能确定一个元素的最终位置，因此它的排序效率较低，不适用于大规模数据的排序。
以下是一个简单选择排序的示例代码（使用C语言实现）：
void selectSort(int *arr,int n) //简单选择排序
{
int i,j,k,temp;
for(i=0;iarr[j])
k = j; //最小值的索引
}
temp = arr[i];
arr[i] = arr[k];
arr[k] = temp;
}
}
二、冒泡排序
冒泡排序是一种简单的排序算法，它重复地遍历要排序的列表，每次比较相邻的两个元素，并将它们交换位置，直到整个列表排序完成。
以下是冒泡排序的伪代码实现：
- 从列表的第一个元素开始，重复遍历列表，直到倒数第二个元素（假设列表长度为n）。
- 对于每次遍历，从第一个元素开始向后比较相邻的两个元素。
- 如果前一个元素大于后一个元素，则交换它们的位置。
- 重复步骤2和3，直到遍历到倒数第二个元素。
- 继续重复步骤1到步骤4，直到列表中的元素全部排好序。
下面是一个使用c实现的冒泡排序算法的例子：
//两两比较，将最大的值依次传递到尾部
void bubleSort(int *arr,int n) //冒泡排序
{
int temp,i,j,flag;
for(i=n-1;i>=1;i--){
flag = 1; //判断数是否是有序的
for(j=1;j<=i;j++){
if(arr[j-1]>arr[j]){
temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
flag = 0;
}
}
if(flag) //如果有序，将直接退出函数
return;
}
}
三、直接插入排序
直接插入排序是一种简单直观的排序算法，其基本思想是将待排序的序列划分为已排序和未排序两部分，初始状态时已排序部分只包含第一个元素，然后逐个将未排序部分的元素插入到已排序部分的合适位置。
具体实现步骤如下：
- 将第一个元素视为已排序部分，将剩余的元素视为未排序部分。
- 从未排序部分依次取出一个元素，将其与已排序部分的元素比较，找到合适的位置插入。
- 将未排序部分的第一个元素插入到已排序部分的合适位置。
- 重复步骤2和步骤3，直到未排序部分为空。
以下是用c实现直接插入排序的示例代码：
//将无序的数插入到有序的序列中
void insertSort(int*arr,int n) //直接插入排序
{
int temp,i,j;
for(i=1;i=0&&temp 四、希尔排序
希尔排序是一种排序算法，属于插入排序的一种改进。它通过将原始数组分割成若干个较小的子数组，分别进行插入排序，然后逐步将子数组的长度缩小，最终完成排序。
希尔排序的基本思想是将原始数组按照一定的增量分组，对每个分组进行插入排序，然后逐步缩小增量，直到增量为1，最后进行一次插入排序。
具体步骤如下：
- 选择一个增量序列，例如，初始增量为n/2，之后每次缩小为原来的一半。
- 对每个增量进行插入排序，即将原始数组分成若干个子数组，对每个子数组进行插入排序。
- 重复步骤2，直到增量为1，进行最后一次插入排序。
希尔排序的时间复杂度取决于增量序列的选择，最好情况下可以达到O(n log n)，最差情况下为O(n^2)。
希尔排序的优点是相对于其他插入排序算法，它可以更快地将小元素移到前面，从而减少整体的移动次数。缺点是增量序列的选择不是很好时，性能可能会较差。
//增量取表长的一半，依次减半直到为1，每取一半的增量都要对数进行直接插入排序
void shellSort(int *arr,int n) //希尔排序
{
int j,i,k,temp,gap;
for(gap=n/2;gap>0;gap/=2){
for(i = gap;i=gap&&arr[j-gap]>arr[j];j-=gap)
arr[j] = arr[j-gap];
arr[j] = temp;
}
}
} 五、快速排序
快速排序是一种常用的排序算法，它通过选择一个基准元素，将待排序序列划分为两部分，一部分比基准元素小，一部分比基准元素大。然后对划分后的两部分序列分别进行快速排序，直到序列为空或只有一个元素。
具体步骤如下：
- 1.选择一个基准元素，通常选择序列的第一个元素。
- 2.将序列分为两部分，左边部分的元素都比基准元素小，右边部分的元素都比基准元素大。
- 3.对左、右两部分序列分别进行快速排序，即递归调用快速排序算法。
- 4.将左、右两部分排序后的序列合并起来，即得到最终的有序序列。
快速排序的时间复杂度为O(nlogn)，是一种效率较高的排序算法。
void quickSort(int*arr,int low,int high) //快速排序
{
int i,j,temp;
i = low; j = high;
if(lowi&&arr[j]>=temp) j--;
if(ii&&arr[i] 六、整体代码实现
#include #include //将最小值跟第一个元素由左到右依次交换
void selectSort(int *arr,int n) //简单选择排序
{
int i,j,k,temp;
for(i=0;iarr[j])
k = j; //最小值的索引
}
temp = arr[i];
arr[i] = arr[k];
arr[k] = temp;
}
}
//两两比较，将最大的值依次传递到尾部
void bubleSort(int *arr,int n) //冒泡排序
{
int temp,i,j,flag;
for(i=n-1;i>=1;i--){
flag = 1; //判断数是否是有序的
for(j=1;j<=i;j++){
if(arr[j-1]>arr[j]){
temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
flag = 0;
}
}
if(flag) //如果有序，将直接退出函数
return;
}
}
//将无序的数插入到有序的序列中
void insertSort(int*arr,int n) //直接插入排序
{
int temp,i,j;
for(i=1;i=0&&temp0;gap/=2){
for(i = gap;i=gap&&arr[j-gap]>arr[j];j-=gap)
arr[j] = arr[j-gap];
arr[j] = temp;
}
}
}
void quickSort(int*arr,int low,int high) //快速排序
{
int i,j,temp;
i = low; j = high;
if(lowi&&arr[j]>=temp) j--;
if(ii&&arr[i]