交换排序:
1.冒泡排序
public static void bubble(int arr[]){
for(int i=1;i<arr.length;i++){//控制次数
for(int j=0;j<arr.length-i;j++){//控制当前比较到那个位置
if(arr[j]>arr[j+1]){
swap(arr,j,j+1);
}
}
}
}
2.快排
public static void quickSort(int a[],int left,int right){
int i;
if(left<right){
i=partition(a,left,right);
quickSort(a,left,i-1);
quickSort(a,i+1,right);
}
}
public static int partition(int a[],int left,int right){
int base = a[left];
while(left<right){
while(left<right && a[right]>=base) {--right;}
a[left] = a[right];
while(left<right && a[left]<=base) {++left;}
a[right] = a[left];
}
a[left] = base;//a[right]=base; right==left;
return left;
}
选择排序
1.直接选择
public static void select(int a[]){
int index;
for(int i=0;i<a.length-1;i++){
index = i;
for(int j=i+1;j<a.length;j++){
if(a[j]<a[index]){
index = j;
}
}
if(index!=i){
swap(a,index,i);
}
}
}
2.堆排序
public static void heap(int[] data)
{
int n = data.length;
for(int i=n/2-1;i>=0;i--){//从中间有叶子节点的数据开始
keepHeap(data,i,n);
}
while (n > 0) {
swap(data, 0, n-1);//把第一个和本次建堆的最后一个交换
keepHeap(data, 0,--n);//排除最后一个继续建堆
}
}
/**
* 建(大/小顶)堆操作
* @param r
* @param index 本次建堆的起始下标
* @param length 本次建堆的数据长度
*/
private static void keepHeap(int[] r, int index,int length) {
int x = r[index];
int j = 2 * index + 1;
while (j < length ) {//注意是: 下标 < 长度(不是 下标<最长的下表)
if (j < length - 1 && r[j] < r[j + 1])//判断是否存在右节点,且和左节点比较大小
++j;
if (r[j] > x) {
r[index] = r[j];//上面小的变成下面大的
index = j;
j = 2 * index + 1; //继续向下
}else{
break;
}
}
r[index] = x;
}
插入排序
1.直接插入排序
public static void insert(int a[]){
for(int i=1;i<a.length;i++){
int t = a[i];
int j = i-1;
while(j>=0 && t<a[j]){
a[j+1] = a[j];
j--;
}
a[j+1] = t;
}
}
2.折半插入排序
public static void halfInsert(int a[]){
for(int i=1;i<a.length;i++){
int t = a[i];
int big = i-1, small = 0;
while(big>=small){
int mid = (big+small)/2;
if(a[mid]<t){
small = mid+1;
}else{
big = mid-1;
}
}
//(i-1)->small 数值 均向前移动一位
for(int j=i;j>small;j--){
a[j] = a[j-1];
}
a[big+1] = t;
}
}
3.希尔排序
方法1.
public static void shell(int a[]){
for(int span=a.length/2;span>=1;span--){
for(int i=span;i<a.length;i++){
int tmp = a[i];
int j = i-span;
while(j>=0 && a[j]>tmp){
a[j+span] = a[j];
j -= span;
}
a[j+span] = tmp;
}
}
}
方法2:
public static void shell2(Number[] data)
{
int span=data.length/7;
if(span==0)span=1;
while(span>=1){
for(int i=0;i<span;i++){
for(int j=i;j<data.length;j=j+span){
//组内直接插入排序
int p = j-span;
Number temp = data[j];
while( p >=0 && data[p].doubleValue() > temp.doubleValue()){
data[p+span] = data[p];
p -=span;
}
data[p + span] = temp;
}
}
span=span/2;
}
}
方法1和2的微妙之处,至于1是在span之内先增加i,遇到块便向后查询
2是先循环一个块上的数据来排序,然后在span之内在递增
二者最外层都是在缩小span;
解释的不是很清楚,需要阅读代码
其他:
归并排序
/**
* 分治和归并
* @param a
* @param low
* @param high
* @param b
*/
public static void mergeSort(int a[],int low,int high,int b[]){
int mid;
if(low<high){
mid = (low+high)/2;//分治位置
mergeSort(a, low, mid, b);
mergeSort(a,mid+1,high,b);
merge(a,low,mid,high,b);//归并
}
}
/**
* 合并两个有序子序列
* @param a
* @param low
* @param mid
* @param high
* @param b 辅助数组
*/
public static void merge(int a[],int low,int mid,int high,int b[]){
int i = low;
int j = mid+1;
int p = 0;
while(i<=mid&&j<=high){
b[p++] = (a[i]<=a[j])?a[i++]:a[j++];
}
//如果子序列1没有合并完则直接复制到辅助数组中去
//复制low mid段未被copy的部分
while(i<=mid){
b[p++] = a[i++];
}
//如果子序列2没有合并完则直接复制到辅助数组中去
//复制mid+1 high段未被copy的部分
while(j<=high){
b[p++] = a[j++];
}
//把辅助数组的元素复制到原来的数组中去
//复制b[0 ~ p-1]到a[low ~ high]
for(p=0,i=low;i<=high;i++,p++){
a[i] = b[p];
}
}
基数排序
暂无
本文参照了网上一些文章,对此如有版权问题,请与我联系,放在这里主要是为了共同学习。
分享到:
相关推荐
堆排序7.java 使用java实现的堆排序堆排序7.java 使用java实现的堆排序堆排序7.java 使用java实现的堆排序堆排序7.java 使用java实现的堆排序堆排序7.java 使用java实现的堆排序堆排序7.java 使用java实现的堆排序堆...
Java实现六种常用排序 并用多线程进行速度比较(其实意义不大) 含有代码
java 实现归并排序,有代码实现,复杂度分析,基本步骤,适合初学者吧,
主要介绍了Java实现拖拽列表项的排序功能,非常不错,具有参考借鉴价值,需要的朋友可以参考下
快速排序算法的Java实现。下载后把Package信息稍作修改即可运行。
Java ip 地址排序Java ip 地址排序Java ip 地址排序Java ip 地址排序
Java实现的常见排序算法.pdfJava实现的常见排序算法.pdfJava实现的常见排序算法.pdfJava实现的常见排序算法.pdfJava实现的常见排序算法.pdfJava实现的常见排序算法.pdf
堆排序12.java 使用java代码实现堆排序12.java 使用java代码实现堆排序12.java 使用java代码实现堆排序12.java 使用java代码实现堆排序12.java 使用java代码实现堆排序12.java 使用java代码实现堆排序12.java 使用...
堆排序10.java 使用java来实现堆排序10.java 使用java来实现堆排序10.java 使用java来实现堆排序10.java 使用java来实现堆排序10.java 使用java来实现堆排序10.java 使用java来实现堆排序10.java 使用java来实现堆...
提供Java版七种排序算法代码大全,包括冒泡排序、选择排序、插入排序、希尔排序、快速排序、归并排序、堆排序
java实现的冒泡排序 很简单一看就懂
实现合并排序,插入排序,希尔排序,快速排序,冒泡排序,桶排序算法的java实现。
java实现的插入排序 都是静态的例子 很简单
提供了Java实现几种常见排序方法和原理介绍
冒泡排序,插入排序,希尔排序,选择排序,堆排序,归并排序,快速排序,桶排序,计数排序,基数排序,TimeSort排序
Java实现堆排序不是C,Java实现堆排序不是C,Java实现堆排序不是C,Java实现堆排序不是C
Java实现的所有排序算法Java实现的所有排序算法
Java实现计数排序不是C,Java实现计数排序不是C,Java实现计数排序不是C
用java实现了10种基础排序,其内容包括: 1.冒泡排序 2.选择排序 3.插入排序 4.快速排序 5.希尔排序 6.归并排序 7.堆排序 8.桶排序 9.基数排序 10.计数排序 如有疑问请私信我