1.冒泡排序
是一种稳定的排序方式,时间复杂度O(n^2)。列出三种逐次优化的实现方法:
1.1 最普通
public class BubbleSortV1 {
public static void bubbleSort(int[] array){
for(int i=0;i<array.length;i++){
for(int j = i+1;j<array.length;j++){
if(array[i]>array[j]){
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
}
}
}
1.2 改进一点,从后往前循环,比较的过程中顺便交换元素位置。
public class BubbleSortV2 {
public static void bubbleSort(int[] array){
for(int i = 0;i<array.length;i++){
for(int j = array.length-1;j>i;j--){
if(array[j]<array[j-1]){
int tmp = array[j];
array[j] = array[j-1];
array[j-1] = tmp;
}
}
}
}
}
1.3 增加标志位,减少无效循环。
public class BubbleSortV3 {
public static void bubbleSort(int[] array){
boolean flag = true;
for(int i = 0;i<array.length&& flag;i++){
flag = false;
for(int j= array.length-1;j>i;j--){
if(array[j]<array[j-1]){
int tmp = array[j];
array[j] = array[j-1];
array[j-1] = tmp;
flag = true;
}
}
}
}
}
2.简单选择排序
冒泡排序的一种,优点在于省略了冒泡排序中频繁的交换操作。是一种稳定的排序方式,时间复杂度O(n^2)
public class SelectSort {
public static void selectSort(int[] array){
for(int i=0;i<array.length;i++){
int m = i;
for(int j=i+1;j<array.length;j++){
if(array[j]<array[m]){
m = j;
}
}
if(i!=m){
int tmp = array[i];
array[i] = array[m];
array[m] = tmp;
}
}
}
}
3.直接插入排序
是一种不稳定的排序方式,时间复杂度为O(n^2),但是性能比冒泡和简单选择排序要好。
public class InsertSort {
public static void insertSort(int[] array){
for(int i=1;i<array.length;i++){
for(int j = i;j>0;j--){
if(array[j]<array[j-1]){
int tmp = array[j];
array[j] = array[j-1];
array[j-1] = tmp;
}else{
break;
}
}
}
}
}
4.希尔排序
希尔排序的基本思路是将待排序列划分成间距为gap的多个子序列,子序列内通过插入排序的方式进行排序,使整个序列趋向于有序,然后不断的缩减gap到1。
希尔排序是一种不稳定的排序方式,时间复杂度为O(NlogN)
public class ShellSort {
public static void shellSort(int[] array){
int length = array.length;
int j;
for(int gap = length/2;gap>0;gap = gap/2){
for(int i = gap;i<length;i++){
int tmp = array[i];
for(j = i; j>=gap&&tmp<array[j-gap]; j=j-gap){
array[j] = array[j-gap];
}
array[j] = tmp;
}
}
}
}
5.堆排序
升序排序使用大顶堆的性质,不断的从堆顶获取值放到序列的最后一位。
堆排序是一种不稳定的排序方式,其最好、最坏、平均时间复杂度均为O(NlogN)
public class HeapSort {
public static void heapSort(int[] array){
for(int i = array.length/2-1;i>=0;i--){
adjustHeap(array,i,array.length);
}
for(int j = array.length-1;j>0;j--){
swap(array,0,j);
adjustHeap(array,0,j);
}
}
public static void adjustHeap(int[] array,int start,int end){
int tmp = array[start];
for(int k = start*2+1;k<end;k=k*2+1){
if(k+1<end&&array[k]<array[k+1]){
++k;
}
if(tmp<array[k]){
array[start] = array[k];
start = k;
}else {
break;
}
}
array[start] = tmp;
}
public static void swap(int[] array,int i,int j){
int tmp = array[i];
array[i]= array[j];
array[j] = tmp;
}
}
6.归并排序
是一种稳定的排序算法,时间复杂度O(NlogN)
public class MergeSort {
public static void mergeSort(int[] array,int left,int right,int[] tmp){
if(left<right){
int mid = (left+right)/2;
mergeSort(array,left,mid,tmp);
mergeSort(array,mid+1,right,tmp);
merge(array,left,mid,right,tmp);
}
}
private static void merge(int[] array,int left,int mid,int right,int[] tmp){
int i = left;
int j = mid+1;
int t = 0;
while(i<=mid && j<=right){
if(array[i]<=array[j]){
tmp[t++] = array[i++];
}else{
tmp[t++] = array[j++];
}
}
while (i<=mid){
tmp[t++] = array[i++];
}
while (j<=right){
tmp[t++] = array[j++];
}
t = 0;
while (left <= right){
array[left++] = tmp[t++];
}
}
}
7.快速排序
快速排序是一种不稳定的排序方法,时间复杂度为O(NlogN)
public class QuickSort {
public static void quickSort(int[] array,int low,int high){
int pivot;
if(low<high){
pivot = partition(array,low,high);
quickSort(array,low,pivot-1);
quickSort(array,pivot+1,high);
}
}
private static int partition(int[] array,int low,int high){
int pivotValue = array[low];
while (low<high){
while(low<high&&array[high]>=pivotValue){
high--;
}
swap(array,low,high);
while(low<high&&array[low]<=pivotValue){
low++;
}
swap(array,low,high);
}
return low;
}
private static void swap(int[] array,int i,int j){
int tmp = array[i];
array[i]= array[j];
array[j] = tmp;
}
}