Kosmos
---我们总得选择一条路去前行---
目录
常见排序算法
常见排序算法
冒泡排序
public int[] bubbleSort(int[] a){
if(a == null ||a.length==0)
{
return a;
}
for(int i = 0;i<a.length-1;i++)
{
for(int j = i+1;j<a.length;j++)
{
if(a[i] > a[j])
{
Util.Util.swap(a,i,j);
}
}
}
return a;
}
//感觉不是很正宗呢 -.-
//两个循环+一个交换
选择排序
package sort;
public class Selection_sort {
public int[] sort(int[] a){//不断的挑选出未排序的最小的数
for (int i=0;i<a.length-1;i++)
{
int flag = a[i];
int minindex = i;
for (int j = i+1;j<a.length;j++)
{
if(a[j] < a[minindex])
{
minindex = j;
}
}
Util.Util.swap(a,i,minindex);
}
return a;
}
}
快速排序
package sort;
import Util.Util;
//分割数组,一边小于pivot,一边大于pivot,然后进行递归
public class quickSort {
//得调用递归,之前不用递归出不来...
public int[] sort(int[] a,int low,int high){
if(low<high)
{
int index = partition(a,low,high);
sort(a,low,index-1);
sort(a,index+1,high);
}
return a;
}
public int partition(int[] a,int low,int high)
{
int pivot = a[low];
while(low<high)
{
while(low<high && pivot <= a[high])
{
high--;
}
a[low] = a[high];//由于有个副本pivot,所以直接覆盖了
while(low<high && pivot >= a[low]){
low++;
}
a[high] = a[low];
}
a[low] = pivot;
return low;
}
}
直接插入排序
package sort;
import Util.Util;
public class insertionSort {
//插入排序也是一种思想很简单的排序方法，
// 它通过比较当前元素和其之前已排好序的元素的大小，
// 找到合适的位置插入，并把插入位置后的元素往后移动。
public int[] sort(int[] a)
{
for (int i = 1;i<a.length;i++)
{
int now = a[i];
int index = i;
for(int j = i;j>=1;j--)
{
if(now < a[j-1])
{
a[j] = a[j-1];
index = j-1;
}
}
a[index] = now;
}
return a;
}
}
//把向后移动的代码改成交换的代码也是可以实现排序的
希尔排序
package sort;
public class ShellSort {
//和直接插入排序差不多,只是多了步长,并不断减少步长
public int[] sort(int[] a)
{
int section = a.length/2;
while(section>=1)
{
for(int i = section;i<a.length;i++)
{
int now = a[i];
int index = i;
for(int j = i-section;j>=0;)
{
if(now < a[j])
{
a[j+section] = a[j];
index = j;
}
j = j-section;
}
a[index] = now;
}
section = section/2;
}
return a;
}
}
归并排序
package sort;
//主要是合并的函数起到排序的作用,利用两个指针进行排序
public class MergeSort {
public int[] sort(int[] a,int left,int right)
{
if(left < right)
{
int mid = (left+right)/2;
sort(a,left,mid);
sort(a,mid+1,right);
merge(a,left,mid,right);
}
return a;
}
public void merge(int[] a, int left, int mid, int right)
{
int[] temp = new int[right-left+1];
int i = left;
int j = mid+1;
int t = 0;//临时数组指针
while(i<=mid&&j<=right)
{
if(a[i] < a[j])
{
temp[t++] = a[i++];
}else{
temp[t++] = a[j++];
}
}
while(i<=mid)
{
temp[t++] = a[i++];
}
while(j<=right)
{
temp[t++] = a[j++];
}
t = 0;
while(left<=right)
a[left++] = temp[t++];
}
}
堆排序
package sort;
import Util.Util;
//0开始的数组,子节点是2*下标+1,2*下标+2
//找到子节点中最大的数,然后和父节点比较大小并交换
public class HeapSort {
public int[] sort(int[] a)
{
for(int i = a.length/2-1;i>=0;i--) //a.length/2-1是最后一个父节点的位置
{
HeapAdjust(a,i,a.length-1);
}
for(int i = a.length-1;i>=0;i--)
{
Util.swap(a,0,i);
HeapAdjust(a,0,i-1);
}
return a;
}
public void HeapAdjust(int[] a,int l,int h)
{
int temp = a[l];
for(int j = 2*l+1;j<=h;j=j*2+1)//得到子节点的最大值
{
if(j+1 <=h && a[j] < a[j+1])
{
j++;
}
if(temp < a[j])
{
a[l] = a[j];
l = j;
}
}
a[l] = temp;
}
}
其他排序还有 桶排序,计数排序,基数排序(都是非比较排序),想偷懒就不写了 👅
标题：常见排序算法