排序
常见的简单排序算法
I. 选择排序
选择排序思路：选择出数组中的最小元素，将它与数组的第一个元素交换位置。再从剩下的元素中选择出最小的元素，将它与数组的第二个元素交换位置。不断进行这样的操作，直到将整个数组排序。
public void sort(int[] arr){
int N = arr.length;
int minIndex = -1;
for(int i=0;i<N;i++){ // arr[i] 是当前元素
minIndex=i;
for(int j=i+1;j<N;j++){ //arr[j] 当前元素后面的元素
if(arr[j]<arr[minIndex]){
minIndex=j;
}
}
if(minIndex==i){ //TODO：这里有个小优化：如果当前元素是最小的则不用交换了
continue;
}
swap(arr,minIndex,i);
}
}
private void swap(int[] arr,int i,int j){
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
@Test
public void test(){
int[] a={3,5,2,4,1,0,-3};
PrintArr.printArray(a);
sort(a);
PrintArr.printArray(a);
}
选择排序需要 ~N2/2 次比较和 ~N 次交换，它的运行时间与输入无关，这个特点使得它对一个已经排序的数组也需要这么多的比较和交换操作。
冒泡排序思路：从左到右不断交换相邻逆序的元素，在一轮的循环之后，可以让未排序的最大元素上浮到右侧。在一轮循环中，如果没有发生交换，就说明数组已经是有序的，此时可以直接退出。
public void sort(int[] arr){
for(int i=arr.length-1;i>0;i--){
for(int j=0;j<i;j++){
if(arr[j]>arr[j+1]){
swap(arr,j,j+1);
}
}
}
}
private void swap(int[] arr,int i,int j){
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
添加一个状态变量对冒泡排序进行优化：
public void sort(int[] arr){
boolean isSorted = false;
for(int i=arr.length-1;i>0 && !isSorted ;i--){
//!isSorted 条件，当 isSorted=true 时说明是有序的，则不需要再执行了        isSorted = true; //初始时认为是有序的
for(int j=0;j<i;j++){
if(arr[j]>arr[j+1]){
isSorted = false; //存在逆序，则是无序的
swap(arr,j,j+1);
}
}
}
}
private void swap(int[] arr,int i,int j){
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
冒泡排序是稳定的排序算法，平均时间复杂度是 O(n^2)。
插入排序思路：每次都将当前元素插入到左侧已经排序的数组中，使得插入之后
左侧数组依然有序。
对于数组 {3, 5, 2, 4, 1}，它具有以下逆序：(3, 2), (3, 1), (5, 2), (5, 4), (5, 1), (2, 1), (4, 1)，插入排序每次只能交换相邻元素，令逆序数量减少 1，因此插入排序需要交换的次数为逆序数量。
插入排序的复杂度取决于数组的初始顺序，如果数组已经部分有序了，逆序较少，那么插入排序会很快。
public void sort(int[] arr){
for(int i=1;i<arr.length;i++){ //默认 arr[0] 已经有序
//a[0,,,i] 已经有序，加入一个元素后，进行一次冒泡(从后向前的)，就必
然是有序的了。
for(int j=i;j>0 && arr[j-1]>arr[j];j--){
swap(arr,j-1,j);
}
}
}
private void swap(int[] arr,int i,int j){
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
IV、希尔排序
对于大规模的数组，插入排序很慢，因为它只能交换相邻的元素，每次只能将逆序数量减少 1。
希尔排序的出现就是为了解决插入排序的这种局限性，它通过交换不相邻的元素，每次可以将逆序数量减少大于 1。
希尔排序思路：希尔排序使用插入排序对间隔 h 的序列进行排序。通过不断减小 h，最后令 h=1，就可以使得整个数组是有序的。
public void sort(int[] arr){
int N = arr.length;
int h=1;
while(h<N/3){
h = 3*h+1;
}
while(h>=1){
for(int i=1;i<N;i++){
for(int j=i;j>=h && arr[j-h]>arr[j];j-=h){
冒泡排序java代码详解
swap(arr,j-h,j);
}
}
h /=3;
}
//注意 h 的值最终会减为 1
}
private void swap(int[] arr,int i,int j){
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
常见的高级排序算法
I、归并排序
归并排序的思想：将数组分成两部分，分别进行排序，然后归并起来。public void sort(int[] arr){
sort(arr,0,arr.length-1);
}
private void sort(int[] arr,int l,int r){
if(l>=r){
return;
}
int mid = (r-l)/2+l;
//对 [l,mid] 进行排序
sort(arr,l,mid);
//对 [mid+1,r] 进行排序
sort(arr,mid+1,r);
//合并这两个有序数组
merge(arr,l,mid,r);
}
//合并两个有序数组
//[l,mid]
//[mid+1,r]
private void merge(int[] arr,int l,int mid,int r){
int[] nums = new int[r-l+1];
int index=0;
int i=l;
int j=mid+1;
while(i<=mid && j<=r){
if(arr[i]<arr[j]){
nums[index++] = arr[i++];
}else{
nums[index++] = arr[j++];
}
}
while(i<=mid){
nums[index++]=arr[i++];
}
while(j<=r){
nums[index++]=arr[j++];
}
index=0;
for(int k=l;k<=r;k++){
arr[k] = nums[index++];
}
}
II、快速排序
快速排序思路：快速排序通过一个切分元素将数组分为两个子数组，左子数组小于等于切分元素，右子数组大于等于切分元素，将这两个子数组排序也就将整个数组排序了。
public void sort(int[] arr){
sort(arr,0,arr.length-1);
}
private void sort(int[] arr,int l,int r){
if(l>=r){
return;
}
int p = partition(arr,l,r);
sort(arr,l,p-1);
sort(arr,p+1,r);
}
private int partition(int[] arr,int l,int r){
int pivot = arr[l];
while(l<r){
while(l<r && arr[r]>=pivot){
r--;
}
arr[l] = arr[r];
while(l<r && arr[l]<=pivot){
l++;
}
arr[r] = arr[l];
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。