赞
踩
public void bubbleSort(int[] array){
for (int i = 0; i < array.length-1; i++) {
boolean flag=false;
for (int j = i; j <array.length-1-i ; j++) {
if (array[j]>array[j+1]){
int temp=array[j];
array[j]=array[j+1];
array[j+1]=temp;
flag=true;
}
}
if (!flag){
return;
}
}
}
public void insertSort(int[] array){
int insertValue=0;
int index=0;
for (int i = 1; i < array.length; i++) {
//提取出要插入的数据
insertValue=array[i];
//放出哨兵向左移动检查可以插入的点
index=i-1;
while (index >=0&&insertValue<array[index]){
array[index+1]=array[index];
index--;
}
if (index+1!=i){
array[index+1]=insertValue;
}
}
}
public void selectSort(int[] array){
for (int i = 0; i <array.length-1 ; i++) {
int min=array[i];
int index=i;
for (int j = i+1; j < array.length; j++) {
if (array[j]<min){
index=j;
min=array[j];
}
}
if (index!=i){
array[index]=array[i];
array[i]=min;
}
}
}
public void shellSort(int[] array){
//gap是步长
//普通插入排序步长是一,这里的希尔插入排序步长不为一
for (int gap = array.length/2; gap > 0; gap/=2) {
//以下与插入排序唯一不同的是步长不为一
int insertValue=0;
int index=0;
for (int i = gap; i < array.length; i++) {
//提取需要插入的数据
insertValue=array[i];
//放出哨兵向前移动gap步长去检查可以插入的点
index=i-gap;
while (index>=0&&insertValue<array[index]){
array[index+gap]=array[index];
index-=gap;
}
if (index!=i-gap){
array[index+gap]=insertValue;
}
}
}
}
//借助另外的temp空间对每层分出来的部分进行治理(合并左右两个有序部分)
public void merge(int[] array,int left,int mid,int right,int[] temp){
int l=left;//左半部分头指针
int r=mid+1;//右半部分头指针
int t=0;//temp数组头指针
while (l<=mid&&r<=right){
//左右两边谁小谁进入temp数组
if (array[l]<array[r]){
temp[t]=array[l];
l++;
}else {
temp[t]=array[r];
r++;
}
t++;
}
//处理左边或右边剩余的部分
while (l<=mid){
temp[t]=array[l];
t++;
l++;
}
while (r<=right){
temp[t]=array[r];
r++;
t++;
}
//把辅助数组temp中的数拷贝进原数组,实现原数组的更新
t=0;
int tempLeft=left;
while (tempLeft<=right){
array[tempLeft]=temp[t];
tempLeft++;
t++;
}
}
//分治
public void divide(int[] array,int left,int right,int[] temp){
if (left<right) {
int mid = (left + right) / 2;
divide(array, left, mid, temp);
divide(array, mid + 1, right, temp);
merge(array, left, mid, right, temp);
}
}
//挖坑法
public void quickSort(int[] array,int left,int right){
if (left<right){
int l=left;
int r=right;
//提取出最右边的数,以最右边数为基准
//挖坑
int x=array[right];
while (l<r){
while (l<r&&array[l]<=x){
l++;
}
if (l<r&&array[l]>x){
//找到比基准数大的挖出,填最右边的坑,此处又形成了新的坑(左边)
array[r]=array[l];
r--;
}
while (l<r&&array[r]>=x){
r--;
}
if (l<r&&array[r]<x){
//找到比基准数小的挖出,填刚才形成的坑(左边),此处又形成了新的坑
array[l]=array[r];
l++;
}
}
array[l]=x;
quickSort(array,left,l-1);
quickSort(array,l+1,right);
}
}
public void radixSort(int[] array){
//先获取最大的数的位数
int max=array[0];
for (int j : array) {
if (j > max) {
max = j;
}
}
int maxLength=(max+"").length();
//创建十个桶
int[][] bucket=new int[10][array.length];
//创建数组记录每个桶内的元素个数
int[] bucketElementCounts=new int[10];
for (int i = 0,n=1; i < maxLength; i++,n*=10) {
//将原数组的数放入桶中
for (int element : array) {
int digitOfElement=element/n%10;
bucket[digitOfElement][bucketElementCounts[digitOfElement]]=element;
bucketElementCounts[digitOfElement]++;
}
//将十个桶中的数放入原数组,实现原数组的更新
int index=0;
for (int j = 0; j < 10; j++) {
if (bucketElementCounts[j]!=0){
for (int k = 0; k < bucketElementCounts[j]; k++) {
array[index++]=bucket[j][k];
}
}
bucketElementCounts[j]=0;
}
}
}
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。