在本篇章中不阐释原理,仅阐述使用java语言实现。
1.冒泡排序(时间复杂度:O(N^2);稳定):
public class sort00 {
public static void sort(Comparable[] a){
for(int i=a.length-1;i>0;i--){
for(int j=0;j<i;j++){
if(greater(a[j],a[j+1])){
exch(a,j,j+1);
}
}
}
}
private static void exch(Comparable[] a, int i, int j) {
Comparable temp=a[i];
a[i]=a[j];
a[j]=temp;
}
private static boolean greater(Comparable a, Comparable b) {
return a.compareTo(b)>0;
}
}
冒泡排序(Bubble Sort),是一种计算机科学领域的较简单的排序算法。它重复地走访过要排序的元素列,依次比较两个相邻的元素,如果顺序(如从大到小、首字母从Z到A)错误就把他们交换过来。走访元素的工作是重复地进行,直到没有相邻元素需要交换,也就是说该元素列已经排序完成。(出自百度百科)
2.选择排序:(时间复杂度:O(N^2);不稳定):
public class sort01 {
public static void sort(Comparable[] a){
for (int i = 0; i <a.length-1 ; i++) {
int minindex=i;
for(int j=i+1;j<a.length;j++){
if(greater(a[minindex],a[j])){
minindex=j;
}
}
exch(a,i,minindex);
}
}
private static void exch(Comparable[] a, int i, int j) {
Comparable temp=a[i];
a[i]=a[j];
a[j]=temp;
}
private static boolean greater(Comparable a, Comparable b) {
return a.compareTo(b)>0;
}
}
选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是:第一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后再从剩余的未排序元素中寻找到最小(大)元素,然后放到已排序的序列的末尾。以此类推,直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。(出自百度百科)
3.插入排序:(时间复杂度:O(N^2);稳定)
public class sort02 {
public static void sort(Comparable[] a){
for (int i = 0; i < a.length - 1; i++) {
for (int j = i; j >=0 ; j--) {
if(geater(a[j],a[j+1])){
exch(a,j,j+1);
}
}
}
}
private static void exch(Comparable[] a,int i,int j){
Comparable temp=a[i];
a[i]=a[j];
a[j]=temp;
}
private static boolean geater(Comparable a,Comparable b){
return a.compareTo(b)>0;
}
}
插入排序,一般也被称为直接插入排序。对于少量元素的排序,它是一个有效的算法 [1] 。插入排序是一种最简单的排序方法,它的基本思想是将一个记录插入到已经排好序的有序表中,从而一个新的、记录数增1的有序表。在其实现过程使用双层循环,外层循环对除了第一个元素之外的所有元素,内层循环对当前元素前面有序表进行待插入位置查找,并进行移动(出自百度百科)
4.希尔排序(不稳定)
public class sort03 {
public static void sort(Comparable[] a){
//1.由数组a的长度确定增长量h的初始值
int h=1;
while (h<a.length/2){
h=2*h+1;
}
//2.希尔排序
while (h>=1){
//排序
//找到待插入的元素
for (int i = h; i < a.length; i++) {
//把待插入的元素插入到有序数列中
for (int j = i; j >=h ; j-=h) {
//带插入元素是a[j],比较a[j]和a[j-h]
if(geater(a[j-h],a[j])){
//交换元素
exch(a,j-h,j);
}else {
//待插入元素已经找到了合适的位置,结束循环
break;
}
}
}
//减小h的值
h=h/2;
}
}
private static void exch(Comparable[] a,int i,int j){
Comparable temp=a[i];
a[i]=a[j];
a[j]=temp;
}
private static boolean geater(Comparable a,Comparable b){
return a.compareTo(b)>0;
}
}
希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至 1 时,整个文件恰被分成一组,算法便终止(出自百度百科)
5.归并排序:时间复杂度为o(nlog(n))
public class sort04 {
//归并排序所需要的辅助数组
private static Comparable[] assist;
//比较v元素是否小于w元素
private static boolean less(Comparable v,Comparable w){
return v.compareTo(w)<0;
}
// 数组元素i和j交换位置
private static void exch(Comparable[] a,int i,int j){
Comparable t=a[i];
a[i]=a[j];
a[j]=t;
}
// 对数组a中元素进行排序
public static void sort(Comparable[] a){
//1.初始化辅助数组assist
assist=new Comparable[a.length];
//2.定义一个lo变量和hi变量,分别记录数组中最小索引和最大索引
int lo=0;
int hi=a.length-1;
//3.调用sort重载方法完成数组a中,从实验lo到索引hi的元素的排序
sort(a,lo,hi);
}
// 对数组a中从lo到hi的元素进行排序
private static void sort(Comparable[] a,int lo,int hi){
if(hi<=lo){
return;
}
// 对lo到hi之间的数据分为两个组
int mid=lo+(hi-lo)/2;
// 分别对每一组数据排序
sort(a,lo,mid);
sort(a,mid+1,hi);
// 把两个组中的数据进行归并
merge(a,lo,mid,hi);
}
// 对数组中从lo到mid为一组,从mid+1到hi为一组,对这两组数据进行归并
private static void merge(Comparable[] a,int lo,int mid,int hi){
//定义三个指针
int i=lo,p1=lo,p2=mid+1;
//遍历移p1指针和p2指针,比较对应索引处的值,找出最小的一个,放到辅助数组的对应索引处
while (p1<=mid && p2<=hi){
//比较对应索引处的值
if(less(a[p1],a[p2])){
assist[i++]=a[p1++];
}else {
assist[i++]=a[p2++];
}
}
//遍历,若p1指针没有走完,那么顺序移动p1指针,把对应的元素放到辅助数组的对应索引处
while (p1<=mid){
assist[i++]=a[p1++];
}
//遍历,若p2指针没有走完,那么顺序移动p2指针,把对应的元素放到辅助数组的对应索引处
while (p2<=hi){
assist[i++]=a[p2++];
}
//把辅助数组中元素复制到原数组中
for (int index = lo; index <=hi ; index++) {
a[index]=assist[index];
}
}
}
归并排序是建立在归并操作上的一种有效,稳定的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并(出自百度百科)
6.快速排序
public class sort05 {
//比较v元素是否小于w元素
private static boolean less(Comparable v,Comparable w){
return v.compareTo(w)<0;
}
// 数组元素i和j交换位置
private static void exch(Comparable[] a,int i,int j){
Comparable t=a[i];
a[i]=a[j];
a[j]=t;
}
// 对数组a中元素进行排序
public static void sort(Comparable[] a){
int lo=0;
int hi=a.length-1;
sort(a,lo,hi);
}
// 对数组a中从lo到hi的元素进行排序
private static void sort(Comparable[] a,int lo,int hi){
//安全性校验
if(hi<=lo){
return;
}
//需要对数组中lo索引到hi索引出的元素进行分组(左子组和右子组)
int partition = partition(a, lo, hi);//返回的是分组分界值所在的索引,分界值位置变换后的索引
//让左子组有序
sort(a,lo,partition-1);
//让右子组有序
sort(a,partition+1,hi);
}
// 对数组a中,从索引lo到索引hi之间的元素进行分组,并返回分组界限对应的索引
public static int partition(Comparable[] a,int lo,int hi){
//确定分界值
Comparable key =a[lo];
//对应两个指针,分别指向待切分元素的最小索引处和最大索引处的下一个位置
int left=lo;
int right=hi+1;
//切分
while (true){
//先从右往左扫描,移动right指针,找到一个比分界值小的元素,停止
while (less(key,a[--right])){
if(right==lo){
break;
}
}
//在从左往右扫描,移动left指针,找到一个比分界值大的元素,停止
while (less(a[++left],key)){
if(left==hi){
break;
}
}
// 判断left>=right;如果成立则证明元素扫描完毕结束循环。若不成立,则交换元素即可
if(left>=right){
break;
}else {
exch(a,left,right);
}
}
//交换分界值
exch(a,lo,right);
return right;
}
}
快速排序(Quicksort),计算机科学词汇,适用领域Pascal,c++等语言,是对冒泡排序算法的一种改进(出自百度百科)
几种排序算法小节:
排序的稳定性:
在乱序数组中,相等元素A,B在排序之后,其位置保持不变,表明此排序算法是稳定的
稳定性的意义:
在多次排序情况下需要使用稳定性的算法,意义在于可以最大保留排序后的结果,减小内存开销
稳定排序:
冒泡、插入、归并、
快速排序和归并排序的区别:
1.归并:先等数量分组各自排序,将分别拍好序的子数组再重新排序成原数组
2.快排:先按标准值分组,这个组不一定是等数量分组,分好组后再各自排序,当所有组拍好序,本数组就有序
时间复杂度:
等分最优:o(nlog(n))
有多少个元素切多少组最坏:o(n^2)
平均复杂度o(nlog(n))