稳定性的定义
假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ri=rj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的。
1.选择排序
选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推，直到第n - 1个元素，第n个元素不用选择了，因为只剩下它一个最大的元素了。
void selectionsort(vector<int>arr,int size)
{
int i,j,min;
i=0;
j=0;
min=0;
for(i=0;i<size;i++)
{
int tmp=arr[min];
for(j=i+1;j<size;j++)
{
if(arr[j]<arr[min])
min=j;
}
swap(arr[min],arr[i]);
}
}
2.堆排序
void percdown(vector<int>a,int i,int n)
{
int child;//孩子节点
int parent;
int tmp=a[i];//临时变量
for(parent=i;parent*2+1<n;parent=child)
{
child=parent*2+1;//当前节点的左孩子节点
//比较左右孩子谁大
if(child!=n-1 && a[child]<a[child+1])//若存在右子节点且右子节点更大
child++;
if(tmp<a[child])
a[parent]=a[child];//下滤
else
break;//找到合适节点
}
a[i]=tmp;
}
void heapsort(vector<int>a,int n)
{
int i;
//初始化堆
for(i=n/2;i>=0;i--)
{
percdown(a,i,n);
}
//排序
for(i=n-1;i>0;i--)
{
swap(a[0],a[i]);
percdown(a,0,i);
}
3.插入排序
插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。
//插入排序
void insertionsort(vector<int>arr,int size)
{
int i,j,tmp;
for(i=1;i<size;i++)
{
tmp=arr[i];
for(j=i;j>0&&arr[j-1]>tmp;j--)
arr[j]=arr[j-1];//挪位置
arr[j]=tmp;
}
}
4.希尔排序
希尔排序就是插入排序的进阶。每次选择一个步长进行插入排序
void shellsort(vector<int>arr,int size)
{
int i,j,gap,tmp;
for(gap=size/2;gap>0;gap/=2)
{
for(i=gap;i<size;i++)
{
tmp=arr[i];
for(j=i;j>0&&arr[j-gap]>tmp;j-=gap)
arr[j]=arr[j-gap];
arr[j]=tmp;
}
}
}
5.冒泡排序
冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。
void bubblesort(vector<int>arr,int size)
{
int i,j;
for(i=0;i<size;i++)
{
for(j=0;j<size-i;j++)
{
if(arr[j]>arr[j+1])
swap(arr[j],arr[j+1]);
}
}
}
6.快速排序
//三路快排
int median3(vector<int>arr,int left,int right)
{
int center=(right+left)/2;
if(arr[left]>arr[center])
swap(arr[left],arr[center]);
if(arr[left]>arr[right])
swap(arr[left],arr[right);
if(arr[center]>arr[right])
swap(arr[center],arr[right]);
swap(arr[center],arr[right-1]);
return arr[right-1];
}
void quicksort(vector<int>arr,int left,int right)
{
int center=median3(arr,left,right);
int i=left;
int j=right;
while(i!=j){
while(arr[i]<arr[center] && i<j)
i++;
while(arr[j]>arr[center] && i<j)
j--;
if(i<j)
swap(arr[i],arr[j]);
else break;
}
swap(arr[i],arr[right]-1);
quicksort(arr,left,i-1);
quicksort(arr,i+1,right);
}
8.归并排序
//归并排序
void merge(vector<int>&arr,int left,int mid,int right)
{
vector<int> res;
int len=right-left+1;
int i=left;
int j=mid+1;
int index=0;
while(i<=mid && j<=right)
{
res[index++] =(arr[i]<=arr[j])? arr[i++] : arr[j++];
}
while(i<=mid)
res[index++]=arr[i++];
while(j<=right)
res[index++]=arr[j++];
for(int k=0;k<len;k++)
arr[left++]=res[k++];
}
void mergesort(vector<int>&arr,int len)
{
if(left == right)
return ;
int mid=(left+right)/2;
merge(arr,left,mid);
merge(arr,mid+1,right);
merge(arr,left,mid,right);
}
稳定性的意义
如果只是简单的进行数字的排序，那么稳定性将毫无意义。
如果排序的内容仅仅是一个复杂对象的某一个数字属性，那么稳定性依旧将毫无意义
如果要排序的内容是一个复杂对象的多个数字属性，但是其原本的初始顺序毫无意义，那么稳定性依旧将毫无意义。
除非要排序的内容是一个复杂对象的多个数字属性，且其原本的初始顺序存在意义，那么我们需要在二次排序的基础上保持原有排序的意义，才需要使用到稳定性的算法，例如要排序的内容是一组原本按照价格高低排序的对象，如今需要按照销量高低排序，使用稳定性算法，可以使得想同销量的对象依旧保持着价格高低的排序展现，只有销量不同的才会重新排序。（当然，如果需求不需要保持初始的排序意义，那么使用稳定性算法依旧将毫无意义）。
网友评论