排序的稳定性：有跳跃式的交换数据就不稳定。例：1 3（1） 4 3（2）
若排序后 ：1 3（1） 3（2） 4 稳定 1 3（2） 3（1） 4 不稳定
以下均以增序为例
1、直接插入排序 ： 把一个新的数据插入到一个已经有序的数列中。
适用于：基本有序、数据量小。
代码：
void Insert(int *arr,int len){ int tmp = 0; for(int i = 1;i<len;i++) { tmp = arr[i]; for(int j = i-1;j>=0 && tmp<arr[j];j--) { arr[j+1] = arr[j]; arr[j] = tmp; } }}
int main(){ int arr[] = {5,0,2,17,3,23,1,5,8,7,9,23,13,14,7}; int len = sizeof(arr)/sizeof(arr[0]); Insert(arr,len); for(int i = 0;i<len;i++) printf("%d ",arr[i]);
}
2、希尔排序 ： 又称”缩小增量排序“，也是属于插入排序的方法。现将整个待排序数列分割为若干个分别进行直接插入排序，
待整个数列基本有序时，再对全体记录进行一次直接插入排序。（越有序越快）
代码：
void Shellsort(int *arr,int len,int n){ int tmp = 0; for(int i = n;i<len;i++) { tmp = arr[i]; for(int j = i-n;j>=0&&tmp<arr[j];j = j-n ) { arr[j+n] = arr[j]; arr[j] = tmp; } } }
int main() { int arr[] = {0,2,4,6,18,5,38,23,3,7,1,9,23,47,67,53,19,27}; int str[] = {5,2,1}; int len = sizeof(arr)/sizeof(arr[0]); int n = sizeof(str)/sizeof(str[0]); for(int i = 0;i<n;i++) Shellsort(arr,len ,str[i]); for(int k = 0;k<len;k++) printf("%d ",arr[k]); }
3、冒泡排序 ： 一次对两个元素进行比较，若后者小于前者则进行交换，重复此过程直至数列有序。
代码：
void Bubblesort(int *arr,int len) { int tmp = 0; for(int i = 0;i<len-1;i++) { for(int j = 0;j<len-i-1;j++) { if(arr[j]>arr[j+1]) { tmp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = tmp; } } } }
int main() { int arr[] = {0,1,1,9,7,3,4,5,7,5}; int len = sizeof(arr)/sizeof(arr[0]); Bubblesort(arr,len); for(int i = 0;i<len;i++) printf("%d ",arr[i]); }
4、简单选择排序 ：通过 n-i 次 关键字间的比较，从 n-i-1 个记录中选出关键字最小的记录，并和第 i 个记录交换。
代码：
void Selectsort(int arr[],int len) { int i,j; int tmp = 0; int count = 0; for(i = 0;i<len-1;i++) { count = i; for(j = i+1;j<len-1;j++) { if(arr[j]<arr[count]) { count = j; } } if(i != count) { tmp = arr[i]; arr[i] = arr[count]; arr[count] = tmp; } } }
int main() { int arr[] = {0,9,3,4,2,7,5,8,6,10}; int len = sizeof(arr)/sizeof(arr[0]); Selectsort(arr,len); for(int i = 0;i<len;i++) printf("%d ",arr[i]); }
5、堆排序
大根堆 ： 父节点数据大于节点数据。 根据父节点找子节点： 左 2*i 右 2*i+1
整个堆数据的长度len ： len/2 最后一个父节点的位置。
小根堆
代码：
void Heapadjust(int arr[],int n ,int len){ int max = arr[n]; for(int j = 2*n;j<=len;j = j*2) { if(arr[j]<arr[j+1]&&j<len) { j++; } if(arr[j]<max) { break; } arr[n] = arr[j]; arr[j] = max; n =j; }}
void Heapsort(int *arr,int len){ for(int i=len/2;i>0;i--) { Heapadjust(arr,i,len-1); } for(int j = len-1;j>0;j--) { int tmp = arr[1]; arr[1] = arr[j]; arr[j] = tmp; Heapadjust(arr, 1, j-1); }}
int main() { int arr[] = {-1,0,2,9,8,3,6,7,1,5,4}; int len = sizeof(arr)/sizeof(arr[0]); Heapsort(arr,len); for(int i = 0;i<len;i++) printf("%d ",arr[i]); }
转载于:https://www.cnblogs.com/97-5-1/p/7397243.html
