数据结构中的排序小结
数据结构中的排序总结
希尔排序：算法实现思想，就是每一次有一个跨度，比如是4，那么我就0 和4 元素比较排好序，1-5元素比较排好序，依次，然后在减小跨度，比如减少到2，那么我 0-2在比较排好序，1-3比较排好序，知道跨度为1时候结束
归并排序：算法思想，就是把一个数组不断的拆分，直到不可拆分，比如数组长度为5，则第一次拆分为2 和3，然后前面两个数比较，排好序，后面三个数相比，排好序，然后再将这两个序列排序（这时候类似与两个集合的合并）
快速排序：实现思想，首先找一个基准点，然后经过一次的排序之后，把比他大的放在右边，比他小的放在左边，然后再去递归形成的两边数组，他们也是各自找一个基准点然后大的排在右边小的排在左边
数据结构中，常用的排序有七种，冒泡排序，插入排序，选择排序，这是三种朴素的排序方法。还有希尔排序，快速排序，堆排序以及归并排序
1，冒泡排序，也叫起泡排序
实现原理：利用双重循环，一共有n个数需要比较找出一个最小或者最大需要比较n-1次，用一个外的for循环控制排序需要循环的次数，用一个内循环，实现冒泡交换，就是前继跟后缀相比，按照从小到大的排序方式，若是前继比后续大，则交换否则不变。这这种排序方法中，还有一种类似于冒泡排序的假冒泡排序。
实现代码：
#include <stdio.h>
//假冒的冒泡排序
void BubbleSort(int a[],int n)
{
int i,j,temp;
for(i = 0 ; i < n-1 ;i++)
for(j = i ; j< n ;j++)
{
if(a[i] > a[j])
{
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
}
//真正的冒泡排序 ，加上了改进的flag标签
void BubbleSort_01(int a[],int n)
{
int i,j,temp;
int flag = 1;
for(i = 0 ; i < n-1 && flag ;i++)
for(j = 0 ; j < n - i - 1;j++)
{
flag = 0;
if(a[j] > a[j+1])
{
temp = a[j+1];
a[j+1] = a[j];
a[j] = temp;
flag = 1;
}
}
}
int main()
{
int i,a[12] = {5,2,6,0,9,1,7,4,8,3,12,-2};
BubbleSort(a,12);
for(i = 0 ;i <12 ; i++)
{
printf("%d ",a[i]);
}
printf("\n");
return 0;
}选择排序：实现思想，通过n-i次关键字的比较，从n-i+1记录中选出最下的记录，并且和第i个记录交换。就没每一次的排序，都需要一个临时变量temp记录最最小的用于交换，没经过一次的交换最小的就会放在在数组的前面。
实现代码：
#include <stdio.h>
void SelectSort(int a[],int n)
{
int i,j,min,temp;
for(i = 0 ;i < n-1 ; i++)
{
min = i;
for(j = i+1 ;j < n ;j++)
{
if(a[j] < a[min])
{
min = j;
}
}
//当最小的不是记录本身则交换
if(min != i)
{
temp = a[i];
a[i] = a[min];
a[min] = temp;
}
}
}
int main()
{
int i,a[12] = {5,2,6,0,9,1,7,4,8,3,12,-2};
SelectSort(a,12);
for(i = 0 ;i <12 ; i++)
{
printf("%d ",a[i]);
}
printf("\n");
return 0;
}
实现代码：
#include <stdio.h>
//直接插入排序
void StraightSort(int a[],int n)
{
int i,j,temp;
for(i = 1; i <= n-1 ;i++)
{
temp = a[i];
for(j = i-1; j >=0 && a[j] > temp;j--)
{
a[j+1] = a[j];
}
a[j+1] = temp;
}
}
int main()
{
int i,a[12] = {5,2,6,0,9,1,7,4,8,3,12,-2};
StraightSort(a,12);
for(i = 0 ;i <12 ; i++)
{
printf("%d",a[i]);
}
printf("\n");
return 0;
}
希尔排序：算法实现思想，就是每一次有一个跨度，比如是4，那么我就0 和4 元素比较排好序，1-5元素比较排好序，依次，然后在减小跨度，比如减少到2，那么我 0-2在比较排好序，1-3比较排好序，知道跨度为1时候结束
实现代码：
#include <stdio.h>
void shellSort(int a[],int n)
{
int i,j,temp;
int gap = n;//跨度
do
{
gap = gap /3 +1;//这里可以选择跨度的变化比例，只要是大于被除数大于2就行
for(i = gap ; i < n ;i++)
{
if(a[i] < a[i-gap])
{
temp = a[i];
for(j = i-gap;j >= 0 && a[j] > temp;j -= gap)
{
a[j+gap] = a[j];
}
a[gap+j] = temp;
}
}
}while(gap > 1);
}
int main()
{
int i,a[12] = {5,2,6,0,9,1,7,4,8,3,12,-2};
shellSort(a,12);
for(i = 0 ;i <12 ; i++)
{
printf("%d",a[i]);
}
printf("\n");
return 0;
}
堆排序：实现思想，就是把一个数组，幻化成一颗完全二叉树，然后构造大顶堆（小顶堆）就是双亲的值一定大于孩子的值，然后再把根节点取出放在数组的末尾（从小到大排列），然后再构造大顶堆，在去根节点存放进数组的n-2位置，往复直到树为空
实现代码：
#include<stdio.h>
//堆排序算法
//交换数组元素
void swap(int k[],int i,int j)
{
int temp;
temp = k[i];
k[i] = k[j];
k[j] = temp;
}
void HeapAdajust(int k[],int s,int n)
{
int i,temp;
temp = k[s];
for(i = 2 *s ;i <= n;i*= 2)
{
if(i < n && k[i] <k[i+1])//假如右子树比左子树大，则i++，就是假如需与双亲节点交换则i的交换
{
i++;
}
if(temp >= k[i])
{
break;//双亲节点比他们都大，不用继续
}
k[s] = k[i];
s = i;
}
k[s] = temp; //把数据还原
}
void HeapSort(int k[],int n)
{
int i;
//构造大顶堆，从倒数的第二行为双亲开始，让他与他的子树对比
for(i = n/2 ;i>0;i--)
{
HeapAdajust(k,i,n);
}
for(i = n ;i > 1; i--)
{
swap(k,1,i);//把最大的元素放进数组的末尾，从后往前排
HeapAdajust(k,1,i-1);//再次构造大顶堆，把最大的元素放在大顶堆的上面
}
}
int main()
{
int i,a[10] = {-1,5,2,6,0,3,9,1,7,4};
HeapSort(a,9);
for(i = 1 ;i <10 ; i++)
{
printf("%d",a[i]);
}
printf("\n");
return 0;
}
归并排序：算法思想，就是把一个数组不断的拆分，直到不可拆分，比如数组长度为5，则第一次拆分为2 和3，然后前面两个数比较，排好序，后面三个数相比，排好序，然后再将这两个序列排序（这时候类似与两个集合的合并）
代码实现（递归实现）
#include <stdio.h>
#define MAXSIZE 10
void merging(int *list1,int list1_size,int *list2,int list2_size)
{
int i,j,k,m;
i = 0,j = 0,k = 0 ;
int temp[MAXSIZE];//存放临时得出结果的数组
while(i<list1_size && j <list2_size)
{
temp[k++] = list1[i] < list2[j] ? list1[i++]: list2[j++];
}
while(i < list1_size)
{
temp[k++] = list1[i++];
}
while(j < list2_size)
{
temp[k++] = list2[j++];
}
//把list1指向排好序列的数组，因为一开始她指向的就是k[]
for(m = 0;m <list2_size+list1_size;m++)
{
list1[m] = temp[m];
}
}
//归并排序递归实现算法
void MergeSort(int k[],int n)
{
if( n > 1)
{
int *list1 = k;//左半部分
int list1_size = n/2;
int *list2 = k+n/2;//有半部分
int list2_size = n - n/2;
MergeSort(list1,list1_size);
MergeSort(list2,list2_size);
merging(list1,list1_size,list2,list2_size);
}
}
int main()
{
int i,a[11] = {5,2,6,0,9,1,7,4,8,3,12};
MergeSort(a,11);
for(i = 0 ;i <11 ; i++)
{
printf("%d ",a[i]);
}
printf("\n");
return 0;
}
快速排序：实现思想，首先找一个基准点，然后经过一次的排序之后，把比他大的放在右边，比他小的放在左边，然后再去递归形成的两边数组，他们也是各自找一个基准点然后大的排在右边小的排在左边
算法实现（递归）
#include <stdio.h>
//快速排序的算法实现
void Swap(int k[],int low,int high)
{
int temp;
temp = k[low];
k[low] = k[high];
k[high] = temp;
}
int Partition(int k[],int low,int high)
{
int point;
point = k[low];
while(low < high)
{
while(low < high && k[high] >= point )
{
high--;
}
Swap(k,low,high);
while(low < high && k[low] <= point )
{
low++;
}
Swap(k,low,high);
}
return low;
}
void QSort(int k[],int low,int high)
{
int point;
if(low < high)
{
point = Partition(k,low,high);
QSort(k,low,point-1);
QSort(k,point + 1,high);
}
}
void QuickSort(int k[],int n )
{
QSort(k ,0 ,n-1);
}
int main()
{
int i,a[11] = {5,2,6,0,9,1,7,4,8,3,12};
QuickSort(a,11);
for(i = 0 ;i <11 ; i++)
{
printf("%d ",a[i]);
}
printf("\n");
return 0;
}