排序-C语言版
2019-07-10 本文已影响0人
Elijah_cs
- 冒泡排序
- 冒泡排序是基于比较的排序，它会遍历若干次要排序的数列，每次遍历时，它都会从前往后依次的比较相邻两个数的大小；如果前者比后者大，则交换它们的位置。这样，一次遍历之后，最大的元素就在数列的末尾！ 采用相同的方法再次遍历时，第二大的元素就被排列在最大元素之前。重复此操作，直到整个数列都有序
- 时间复杂度：排序n个数据要n-1次遍历，每次遍历需要两两n-1-count次，count为已经排好序的个数，所以时间复杂度为O(n*n)，空间复杂度显然为O(1)。
- 稳定性：在排序的过程中，只有满足了大于或者小于才交换，相等时不交换，并且也没有跨越式的交换，所以是稳定的
- 优化：每次在排序一个数时，判断交换操作是否发生，要是没有发生可以认为当前以及有序，可以提前结束循环。
稳定性的定义：假设在数列中，a[i]=a[j]，若在排序之前，a[i]在a[j]前面，并且在排序之后，a[i]仍然在a[j]前面，那么这个算法是稳定的。
#include<stdio.h>
void bubble_Sort(int data[],int len)
{
int i,j,temp;
for(j=0;j<len-1;j++) //排序len个数据，需要经过len-1此循环，因为排序好len-1个后，最后一个就在他该在的位置
{
for(i=0;i<len-j-1;i++) // 每次排序会把当前最大值固定到一个位置，所以每次排序时比较的部分不一样，当第一次排序j=0时，i=0-8,比较了整个数组
{
if(data[i]>data[i+1])//比较大小，大的往后
{
temp = data[i];
data[i] = data[i+1];
data[i+1] = temp;
}
}
}
return ;
}
int main()
{
int data[10] = {2,4,7,1,9,3,6,5,8,0};
int i =0;
for(i=0;i<10;i++)
{
printf("%d ",data[i]);
}
bubble_Sort(data,10);
printf("\n");
for(i=0;i<10;i++)
{
printf("%d ",data[i]);
}
printf("\n");
return 0;
}
- 选择排序
- 选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
- 时间复杂度：排序n个数据要找n-1次极值，遍历n-1遍，每一遍子n-count个数值中寻找，则时间复杂度为O(n*n),空间复杂度为O(1)
- 稳定性：不稳定，他会把值直接转移到后面，例如序列【 3，3，1】，那么第一个3在第一次遍历会放到三号位去，显然不稳定。
#include<stdio.h>
void selection_Sort(int data[],int size)
{
int i,j,max;
int max_index;
int pos;
for(pos = 0;pos<size-1;pos++) //每次找出极值放入到下标pos的位置
{
max = data[pos];
for(i = pos+1;i<size;i++) //pos之前的已经排好序了，所以从pos后开始遍历寻找机值
{
if(data[i] < max)
{
max = data[i];
max_index = i; //找到极值的下标
}
}
//交换值
data[max_index] = data[pos];
data[pos] = max;
}
}
int main()
{
int data[10] = {2,4,7,1,9,3,6,5,8,0};
int i =0;
for(i=0;i<10;i++)
{
printf("%d ",data[i]);
}
selection_Sort(data,10);
printf("\n");
for(i=0;i<10;i++)
{
printf("%d ",data[i]);
}
printf("\n");
return 0;
}
- 插入排序
- 插入排序是这样的：现在有已经有序的序列a[0,1....i-1]以及待排序的序列a[i,i+1,....n-1]，现在遍历到index=i,即找到a[i]插入到a[0,1...i-1]序列的位置，pos,然后a[pos]-a[i-1]后的数据往后移动一个位置，将a[i]插入到a[pos],最初我们可以认为a[0]是一个有序序列。
- 时间复杂度：排序n个数据需要寻找n-1次位置，因为默认a[0]有序，后续的都是无序，都需要寻找位置，同样的，每次寻找位置，移动数据需要O(n)的时间复杂度，所以时间复杂度为O(n*n)。空间复杂度为O(1)
- 稳定性： 是稳定的，例如假如a[i] = a[i+k] = 5,那么它遍历到a[i]时插入的位置为pos,到a[i+k]时，a[pos]==a[i+k]继续往前，发现a[pos+1]>a[i+k]，那么该插入的位置为pos+1，即可知位置顺序仍然不变
#include<stdio.h>
void insert_Sort(int data[],int size)
{
int i,j;
int pos;
int temp;
int flag;
for(i=1;i<size;i++) //找到当前位置为i应该插入的位置，此时i=1,那么与data[0]比较即可，当i=2,需要与data[0,1]比较找到位置
{
flag = 0;
pos = 0;
for(j=0;j<i;j++)
{
if(data[j]>data[i]) //找到第一个大于的位置，即是我们需要插入的位置
{
pos = j;
flag = 1;
break;
}
}
if(flag)
{
temp = data[i];
//把a[pos- i-1]移动一位到a[pos+1 - i],把data[i]复制到data[pos]
for(j=i-1;j>=pos;j--)
data[j+1] = data[j];
data[pos] = temp;
}
}
}
int main()
{
int data[10] = {2,4,7,1,9,3,6,5,8,0};
int i =0;
for(i=0;i<10;i++)
{
printf("%d ",data[i]);
}
insert_Sort(data,10);
printf("\n");
for(i=0;i<10;i++)
{
printf("%d ",data[i]);
}
printf("\n");
return 0;
}
//
更为简单的实现
void insertion_sort(int arr[], int len){
int i,j,temp;
for (i=1;i<len;i++){
temp = arr[i];
//从后往前遍历，不符合的时候直接把数据向后移动一个位置，直到找到第一个符合的值，
for (j=i;j>0 && arr[j-1]>temp;j--) //当前的j-1大于temp,那么往后移动
//循环结束的条件为j=0或者arr[j-1]<=temp，那么可知arr[j]>temp的，所以temp插入的位置为j,又可知在之前的遍历中arr[j]已经移动到前一个了，所以后续直接赋值即可
arr[j] = arr[j-1];
arr[j] = temp;
}
}
- 希尔排序
- 希尔排序是对插入排序的改进，它是基于插入排序的两个特点提出的改进：
- 插入排序在对几乎有序的序列操作时，效率高，可以达到线性排序的时间
- 插入排序低效是因为它每次将数据移动一位
排序的步骤是这样的：选取间隔gap=len/2,然后以间隔分为祭祖，例如a[0, 0+gap, 0+gap+ gap...]可以认为是同一组，然后分别对这些组进行插入排序，排序完后以一定的规律改变gap，直到gap==1即插入排序，完成这次希尔排序。
- 时间复杂度： 不好界定，一般小于O(n*n).空间复杂度为O(1)
- 稳定性：不稳定的，考虑这样一个序列5，5，2，7，6，9，当gap=2时，显然第一个5会放到index=2的地方，二第二个5位置不变，显然不稳定
#include<stdio.h>
void insert_Sort(int data[],int size)
{
int i,j,temp;
for(i=1;i<size;i++)
{
temp = data[i];
for(j=i;j>0&&data[j-1]>temp;j--)
data[j] = data[j-1];
data[j] = temp;
}
}
void shell_sort(int arr[], int len) {
int gap, i, j;
int temp;
for (gap = len >> 1; gap > 0; gap = gap >> 1) //gap一开始为size的一般，结束条件为gap=1排序完成后即gap=1>>2=0
for (i = gap; i < len; i++) {//因为现在是以gap为间隔划分为多组，那么每组的开头默认为有序，即data[0 - gap-1]，所以从gap开始判断其插入的位置
temp = arr[i];
for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap) //先拿data[i-gap]与data[i]比较，再拿data[i-gap-gap]和data[i]比较，直到找到应该插入的位置，边比较边移动位置，可以看到之前插入排序的gap=1现在的gap可变
arr[j + gap] = arr[j];
arr[j + gap] = temp;
}
}
int main()
{
int data[10] = {2,4,7,1,9,3,6,5,8,0};
int i =0;
for(i=0;i<10;i++)
{
printf("%d ",data[i]);
>}
insert_Sort(data,10);
printf("\n");
for(i=0;i<10;i++)
{
printf("%d ",data[i]);
}
printf("\n");
return 0;
}
- 归并排序
把一个数组分为两部分p1,p2，然后把这两部分又划分为两部分p11,p12,p21,p22，一直这样划分直到有序，然后再合并有序的部分形成一个整体，例如当p21,p22有序，那么合并排序后得到有序的p2，同理也可以获得有序的p1，然后合并p1,p2并排序即可得到有序的序列。归并排序实际上是一个划分与合并的过程。
void merge_sort_recursive(int arr[], int reg[], int start, int end) {
//递归结束条件是start>=end，说明当start=end时，就是划分到最底层，每一个元素为一组，为有序序列
if (start >= end)
return;
int len = end - start, mid = (len >> 1) + start;
int start1 = start, end1 = mid;
int start2 = mid + 1, end2 = end;
//要把start到end排好序，先排序start1,end1和start2，end2
merge_sort_recursive(arr, reg, start1, end1);//递归调用函数
merge_sort_recursive(arr, reg, start2, end2);
int k = start;
while (start1 <= end1 && start2 <= end2) //start1-end1和start-end2都还没有排好序，每次选择一个较小的放入大reg数组去，直到其中一个完全插入到reg数组
reg[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
//把剩下未插入到reg数组的插入进去，这两个while只有一个会执行，因为其中一个已经不满足条件了
while (start1 <= end1)
reg[k++] = arr[start1++];
while (start2 <= end2)
reg[k++] = arr[start2++];
for (k = start; k <= end; k++)
arr[k] = reg[k];
}
void merge_sort(int arr[], const int len) {
int reg[len];
merge_sort_recursive(arr, reg, 0, len - 1);
}
- 快速排序
- 堆排序
