简单选择排序
思路：选出最小的元素，放在第一个位置。之后在剩下的元素中，选出最小的元素。放在第二个位置.........以此类推，直到完毕排序。
package h;
public class MyA
{
static void selectOne(int[] a, int begin)
{
int p = begin; //如果修正法
for(int i=begin+1; i<a.length; i++){
if(a[i] < a[p]) p = i; //记录最小元素所在位置
}
{int tmp = a[p]; a[p] = a[begin]; a[begin] = tmp; } //交换元素
}
static void show(int[] a)
{
for(int i=0; i<a.length; i++) System.out.print(a[i] + " ");
System.out.println();
}
public static void main(String[] args)
{
int[] a = {12,8,3,5,16,22,9,14,2,17};
show(a);
for(int k=0; k<a.length-1; k++){
selectOne(a, k);
show(a);
}
}
}
插入排序
思路：把新元素加到已经有序的队列中
public class MyA
{
// 第k项插入到前边的序列中
static void insertOne(int[] a, int k)
{
for(int i=0; i<=k; i++){
if(a[i]>=a[k]){ //找到了插入的位置
int tmp = a[k];
for(int j=k-1; j>=i; j--) a[j+1] = a[j];
a[i] = tmp;
break;
}
}
}
static void show(int[] a)
{
for(int i=0; i<a.length; i++) System.out.print(a[i] + " ");
System.out.println();
}
public static void main(String[] args)
{
int[] a = {15,22,13,9,16,23,18,4,33,25,14};
show(a);
for(int i=1; i<a.length; i++){
insertOne(a,i);
show(a);
}
}
}
高速排序
思路：以一个元素作为标尺，将数据分成两块。一块是小于标尺元素大小的。还有一块是大于等于标尺元素大小的。之后再进行递归。
将刚才分成的两块依照之前的方法再次进行高速排序，直到改分区（块）内没有须要排序的元素。
package j;
class MyA
{
static void show(int[] a)
{
for(int i=0; i<a.length; i++) System.out.print(a[i] + " ");
System.out.println();
}
static void quickSort(int[] a, int begin, int end)
{
if(end-begin<=1) return;
int x = a[begin]; // 标尺
int p1 = begin;
int p2 = end;
boolean dr = true; // 比較方向 一次左一次右
L1: while(p1<p2){
if(dr){
for(int i=p2; i>p1; i--){
if(a[i] <= x){
a[p1++] = a[i];
p2 = i;
dr = !dr;
continue L1;
}
}
p2 = p1;
}
else{
for(int i=p1; i<p2; i++){
if(a[i] >= x){
a[p2--] = a[i];
p1 = i;
dr = !dr;
continue L1;
}
}
p1 = p2;
}
}
a[p1] = x;
quickSort(a,begin,p1-1);
quickSort(a,p1+1,end);
}
public static void main(String[] args)
{
int[] a = {15,22,13,9,16,33,15,23,18,4,33,25,14};
show(a);
quickSort(a, 0, a.length-1);
show(a);
}
}
希尔排序
思路：因为原始数据的有序性对排序时间的长短非常一定的影响。按一定的步长对数据进行分组。使用插入排序法进行排序。之后不断的减少步长。直到步长为1。
public class MyA
{
//希尔排序之中的一个趟排序, dk 为步长
static void shellOne(int[] data, int dk)
{
for(int k=0; k<dk;k++){
//子组做简单插入排序
for(int i=1; k+i*dk<data.length; i++){
//确定插入位置
for(int j=0; j<=i; j++){
if(data[k+j*dk] >= data[k+i*dk]){
int tmp = data[k+i*dk];
for(int p=i-1; p>=j;p--) data[k+(p+1)*dk] = data[k+p*dk];
data[k+j*dk] = tmp;
break;
}
}
}
}
}
static void show(int[] data)
{
for(int i=0; i<data.length; i++) System.out.print(data[i] + " ");
System.out.println();
}
public static void main(String[] args)
{
int[] a = {49,38,65,97,76,13,27,49,55,4};
show(a);
shellOne(a,5);
show(a);
shellOne(a,3);
show(a);
shellOne(a,1);
show(a);
}
}
冒泡排序
思路：相邻元素之间进行比較。将大数放在后面。一趟排序之后则把最大数放到了末尾。多次排序就可以。
这样把小数往前移动，就像把大石头沉入海底，小石头冒泡浮上去。
package g;
public class MyA
{
static void bubbleOne(int[] a, int n)
{
for(int i=0; i<n; i++){
if(a[i] > a[i+1]) { int tmp = a[i]; a[i]=a[i+1]; a[i+1]= tmp;}
}
}
static void show(int[] a)
{
for(int i=0; i<a.length; i++) System.out.print(a[i] + " ");
System.out.println();
}
public static void main(String[] args)
{
int[] a = {3,15,9,18,22,16,5,12,7};
show(a);
for(int k=0; k<a.length-1; k++){
bubbleOne(a, a.length-k-1);
show(a);
}
}
}