这是一个典型冒泡排序的例子,如果成绩都存储在a这个数组当中,经过下面的运算就是排序过的 /** * 这是一个典型的冒泡排序 * @author Administrator * */ public class MaoPao { public static void main(String[] args) { int[] a = new int[] { 4, 2, 1, 3, 5 }; for (int i = 0; i < a.length; i++) { for (int j = 0; j < i; j++) { if (a[j] > a[j + 1]) { int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t; } }
} for(int s:a){ System.out.println(s); } }}
int[] a = new int[] { 4, 2, 1, 3, 5 }; for (int i = 0; i < a.length; i++) { for (int j = 0; j < i; j++) { if (a[j] > a[j + 1]) { int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t; } }
} for(int s:a){ System.out.println(s); }
class zyfsort { public static void main (String[] args) { int gohome[] = new int[]{12,7,54,21,1,4,65,76,34,9,3,6}; System.out.println("插入排序算法"); // InsertionSort(gohome); System.out.println("-------------------------------------------"); System.out.println("选择排序算法"); // SelectSort(gohome); System.out.println("-------------------------------------------"); System.out.println("冒泡排序算法"); // BubbleSort(gohome); System.out.println("-------------------------------------------"); gohome =QuickSort(gohome);
for (int t=0; t<gohome.length;t++) { System.out.print(gohome[t]+"--"); } }
//插入排序算法 public static void InsertionSort(int[] goal) { for (int i = 1; i<goal.length; i++) { int now = i; int frank = goal[i]; while (now>0 && goal[now-1] <= frank) { goal[now]=goal[now-1]; now--; } goal[now]=frank;
}
for (int t=0; t<goal.length;t++) { System.out.print(goal[t]+"--"); } }
//选择排序算法 public static void SelectSort(int[] goal) { int max; int stmp; for (int i = 0; i<goal.length-1; i++) { max=i; for (int j = i+1; j<goal.length; j++) if(goal[j]>goal[max]) max=j;
} /** * 归并排序 * @param a * @param left * @param right */ public static void mergeSort(int a[] , int left , int right) { System.out.println("这是归并排序"); if(left < right) { int middle = (left + right)/2;
mergeSort(a , left , middle); mergeSort(a , middle+1 , right);
merge1(a , left , middle , right); }
}
/** * 使用哨兵 * @param a * @param left * @param middle * @param right */ public static void merge(int a[],int left, int middle, int right) { int n1 = middle - left + 1; int n2 = right - middle; int[] L = new int[n1 + 1] , R = new int[n2 + 1];
for(int i = 0 ; i < L.length - 1 ; i++) { L[i] = a[left + i]; }
for(int i=0 , j=0 , k = left ; k <= right ; k++) { if(L[i] <= R[j]) { a[k] = L[i]; i++; } else { a[k] = R[j]; j++; } } }
/** * 不使用哨兵 * @param a * @param left * @param middle * @param right */ public static void merge1(int a[],int left, int middle, int right) { int n1 = middle - left + 1; int n2 = right - middle; int[] L = new int[n1] , R = new int[n2];
for(int i = 0 ; i < L.length ; i++) { L[i] = a[left + i]; }
int[] a = {6,3,2,6,3,2,9,7};
sort(a);
print(a);
}
private static void print(int [] a) {
for(int i: a) System.out.print(i + " ");
System.out.println();
}
//冒泡排序
private static void sort(int[] a) {
int temp;
for(int i=a.length-1; i>0; i--) {
for(int j=0; j<i; j++) {
if(a[j] > a[j+1]) {
temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}
}
/**
* 这是一个典型的冒泡排序
* @author Administrator
*
*/
public class MaoPao {
public static void main(String[] args) {
int[] a = new int[] { 4, 2, 1, 3, 5 }; for (int i = 0; i < a.length; i++) {
for (int j = 0; j < i; j++) {
if (a[j] > a[j + 1]) {
int t = a[j];
a[j] = a[j + 1];
a[j + 1] = t;
}
}
}
for(int s:a){
System.out.println(s);
}
}}
for (int j = 0; j < i; j++) {
if (a[j] > a[j + 1]) {
int t = a[j];
a[j] = a[j + 1];
a[j + 1] = t;
}
}
}
for(int s:a){
System.out.println(s);
}
public static void main (String[] args) {
int gohome[] = new int[]{12,7,54,21,1,4,65,76,34,9,3,6};
System.out.println("插入排序算法");
// InsertionSort(gohome);
System.out.println("-------------------------------------------");
System.out.println("选择排序算法");
// SelectSort(gohome);
System.out.println("-------------------------------------------");
System.out.println("冒泡排序算法");
// BubbleSort(gohome);
System.out.println("-------------------------------------------");
gohome =QuickSort(gohome);
for (int t=0; t<gohome.length;t++)
{
System.out.print(gohome[t]+"--");
}
}
//插入排序算法
public static void InsertionSort(int[] goal)
{
for (int i = 1; i<goal.length; i++)
{ int now = i;
int frank = goal[i];
while (now>0 && goal[now-1] <= frank)
{
goal[now]=goal[now-1];
now--;
}
goal[now]=frank;
}
for (int t=0; t<goal.length;t++)
{
System.out.print(goal[t]+"--");
}
}
//选择排序算法
public static void SelectSort(int[] goal)
{
int max;
int stmp;
for (int i = 0; i<goal.length-1; i++)
{
max=i;
for (int j = i+1; j<goal.length; j++)
if(goal[j]>goal[max])
max=j;
stmp = goal[i];
goal[i]=goal[max];
goal[max]=stmp;
}
for (int t=0; t<goal.length;t++)
{
System.out.print(goal[t]+"--");
}
}
//冒泡排序算法
public static void BubbleSort(int[] goal)
{ int stmp;
for (int i = 1; i< goal.length; i++)
{
for(int j=0; j<i;j++)
{
if(goal[i]>goal[j])
{
stmp=goal[i];
goal[i]=goal[j];
goal[j]=stmp;
}
}
}
for (int t=0; t<goal.length;t++)
{
System.out.print(goal[t]+"--");
}
}
//快速排序算法
public static int[] QuickSort(int[] number) {
QuickSort(number, 0, number.length-1);
return number ;
}
private static void QuickSort(int[] number,int left, int right) {
int stmp;
if(left < right) {
System.out.println(left+" | "+right+" | "+(left+right)/2);
int s = number[(left+right)/2];
int i = left - 1;
int j = right + 1;
while(true) {
// 向右找
while(number[++i] > s) ;
// 向左找
while(number[--j] < s) ;
if(i >= j)
break;
stmp = number[i];
number[i] = number[j];
number[j] = stmp;
}
QuickSort(number, left, i-1); // 对左边进行递回
QuickSort(number, j+1, right); // 对右边进行递回
}
}
}
* 冒泡排序算法
*/
public static void bubbleSort(int a[])
{
System.out.println("这是冒泡排序");
int n = a.length;
for(int i = 0; i< n-1; i++) // n个数需要n-1趟比较
{
for(int j = 0; j<n-1-i; j++ ) //每一趟需要的比较次数,有i+j=n-1的关系
{
if(a[j]>a[j+1])
{
a[j] = a[j]^a[j+1];
a[j+1] = a[j]^a[j+1];
a[j] = a[j]^a[j+1];
}
}
}
}
/**
* 改进的冒泡排序算法
* 对已排好序的数组,可以终止算法,不再进行比较
*/
public static void bubbleSort2(int a[])
{
System.out.println("这是改进的冒泡排序");
int n = a.length;
int exchange =0; //记录交换次数,如果在一趟比较中交换次数为0,则说明已排好序!
for(int i = 0; i< n-1; i++) // n个数需要n-1趟比较
{
exchange=0;
for(int j = 0; j<n-1-i; j++ ) //每一趟需要的比较次数,有i+j=n-1的关系
{
if(a[j]>a[j+1])
{
a[j] = a[j]^a[j+1];
a[j+1] = a[j]^a[j+1];
a[j] = a[j]^a[j+1];
exchange++;
}
}
if(exchange==0)
break;
}
}
public class Algorithms { public static void p(Object o)
{
System.out.println(o);
}
public static void p()
{
System.out.println();
}
public static void pt(Object b)
{
System.out.print(b);
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub int[] a = {9,2,5,4,7,2,3,1,8};
p("未排序:");
for(int i=0;i<a.length;i++)
pt(a[i]+" ");
p();
p();
// insertSort2(a); //插入排序
// mergeSort(a , 0 , a.length-1); //归并排序
// insertSort(a , 9); //插入排序递归版本
// bubbleSort(a); //冒泡排序
// bubbleSort2(a); //冒泡排序改进
selectSort(a); //选择排序
p();
p("排序:");
for(int i=0;i<a.length;i++)
pt(a[i]+"_");
} /**
* 插入排序
* @param a
*/
public static void insertSort(int a[])
{
System.out.println("这是插入排序");
int i=0, j=0, key=0;
for(i = 1 ; i < a.length ; i++)
{
key = a[i];
for(j=i-1 ; j >= 0 ; j--)
{
if(a[j] > key)
{
a[j+1]=a[j];
}
else
{
break;
}
}
a[j+1]=key;
}
}
public static void insertSort2(int a[])
{
System.out.println("这是插入排序");
int i=0, j=0, key=0;
for(i = 1 ; i < a.length ; i++)
{
key = a[i];
j=i;
while(--j >= 0 && a[j] > key)
{
a[j+1]=a[j];
}
a[j+1]=key;
}
}
/**
* 插入排序递归版本
*/
public static void insertSort(int a[] , int n)
{
System.out.println("这是插入排序(递归)");
if(n>1)
{
insertSort(a , n-1);
insert(a , n);
}
}
public static void insert(int a[] , int n)
{
int tmp = a[n-1];
for(int i=0;i<n-1;i++)
{
if(tmp>a[i])
continue;
else
{
for(int j=n-1;j>i;j--)
a[j]=a[j-1];
a[i] = tmp;
break;
}
}
}
/**
* 归并排序
* @param a
* @param left
* @param right
*/
public static void mergeSort(int a[] , int left , int right)
{
System.out.println("这是归并排序");
if(left < right)
{
int middle = (left + right)/2;
mergeSort(a , left , middle);
mergeSort(a , middle+1 , right);
merge1(a , left , middle , right);
}
}
/**
* 使用哨兵
* @param a
* @param left
* @param middle
* @param right
*/
public static void merge(int a[],int left, int middle, int right)
{
int n1 = middle - left + 1;
int n2 = right - middle;
int[] L = new int[n1 + 1] , R = new int[n2 + 1];
for(int i = 0 ; i < L.length - 1 ; i++)
{
L[i] = a[left + i];
}
for(int j = 0 ; j < R.length - 1; j++)
{
R[j] = a[middle + 1 + j];
}
//哨兵
L[L.length - 1] = 999;
R[R.length - 1] = 999;
// System.out.println();
// System.out.println("L:");
// for(int i=0;i<L.length;i++)
// System.out.print(" "+L[i]);
// System.out.println();
// System.out.println("R:");
// for(int i=0;i<R.length;i++)
// System.out.print(" "+ R[i]);
// System.out.println();
for(int i=0 , j=0 , k = left ; k <= right ; k++)
{
if(L[i] <= R[j])
{
a[k] = L[i];
i++;
}
else
{
a[k] = R[j];
j++;
}
}
}
/**
* 不使用哨兵
* @param a
* @param left
* @param middle
* @param right
*/
public static void merge1(int a[],int left, int middle, int right)
{
int n1 = middle - left + 1;
int n2 = right - middle;
int[] L = new int[n1] , R = new int[n2];
for(int i = 0 ; i < L.length ; i++)
{
L[i] = a[left + i];
}
for(int j = 0 ; j < R.length ; j++)
{
R[j] = a[middle + 1 + j];
}
int i=0 , j=0 , k = 0;
for( k = left ; i<n1 && j<n2; k++)
{
if(L[i] <= R[j])
{
a[k] = L[i];
i++;
}
else
{
a[k] = R[j];
j++;
}
}
while(i<n1)
{
a[k++] = L[i++];
}
while(j<n2)
{
a[k++] = R[j++];
}
}
/**
* 冒泡排序算法
*/
public static void bubbleSort(int a[])
{
System.out.println("这是冒泡排序");
int n = a.length;
for(int i = 0; i< n-1; i++) // n个数需要n-1趟比较
{
for(int j = 0; j<n-1-i; j++ ) //每一趟需要的比较次数,有i+j=n-1的关系
{
if(a[j]>a[j+1])
{
a[j] = a[j]^a[j+1];
a[j+1] = a[j]^a[j+1];
a[j] = a[j]^a[j+1];
}
}
}
}
/**
* 改进的冒泡排序算法
* 对已排好序的数组,可以终止算法,不再进行比较
*/
public static void bubbleSort2(int a[])
{
System.out.println("这是改进的冒泡排序");
int n = a.length;
int exchange =0; //记录交换次数,如果在一趟比较中交换次数为0,则说明已排好序!
for(int i = 0; i< n-1; i++) // n个数需要n-1趟比较
{
exchange=0;
for(int j = 0; j<n-1-i; j++ ) //每一趟需要的比较次数,有i+j=n-1的关系
{
if(a[j]>a[j+1])
{
a[j] = a[j]^a[j+1];
a[j+1] = a[j]^a[j+1];
a[j] = a[j]^a[j+1];
exchange++;
}
}
if(exchange==0)
break;
}
}
/**
* 选择排序
*/
public static void selectSort(int a[])
{
p("这是选择排序!");
for(int i=0;i<a.length;i++)
{
for(int j=i+1;j<a.length;j++)
{
if(a[i]>a[j])
{
a[i] = a[i]^a[j];
a[j] = a[i]^a[j];
a[i] = a[i]^a[j];
}
}
}
}
}