大学讲师,中国首批AP计算机教师,著有中国第一套,历经五年实践证明深受学生欢迎的成功的AP计算机双语教材,2013年以93%的满分率开创了中国AP计算机成功的先河,远远超出全美26.6%的满分率,为中国AP计算机教学树立了典范,并在同年加拿大计算机竞赛中勇夺桂冠,任教学生获哥伦比亚大学,麻省理工学院,卡耐基梅隆大学,宾夕法尼亚大学,康奈尔大学,西北大学等学校录取,远程学生遍及北京、长春、南京、重庆、广州、济南, 深圳、成都、费城,洛杉矶,加州,宾州,新罕布什尔州等地,希望借此平台为信息技术的发展做出贡献！
import java.util.Random;
/**
* @author George
* @date:2011-1-31 18:42:28
*/
public class Sort {
public static void OutputArray(int[] array) {
for (int data : array) {
System.out.print(data + " ");
}
System.out.println();
}
public static int[] createArray() {
int array[] = new int[10];
Random r = new Random();
for (int i = 0; i < 10; i++) {
array[i] = r.nextInt(100);
}
System.out.println("==========原始数组===========");
OutputArray(array);
return array;
}
/**
* 冒泡排序----交换排序的一种
* 方法：相邻两元素进行比较，如有需要则进行交换，每完成一次循环就将最大元素排在最后（如从小到大排序），
* 下一次循环是将其他的数进行类似操作。*/
public static void bubbleSort(int[] array, String sortType) {
int temp;
if (sortType.equals("asc")) { //从小排到大
//比较的轮数
for (int i = 0; i < array.length - 1; i++) {
//将相邻两个数进行比较，较大的数下沉，较小的数上升
for (int j = 0; j < array.length - i-1; j++) {
if (array[j] > array[j + 1]) {
temp=array[j];
array[j]=array[j+1];
array[j+1]=temp;
}
}
}
} else if (sortType.equals("desc")) { //倒排序，从大排到小
//比较的轮数
for (int i =0; i <array.length-1; i++) {
//将相邻两个数进行比较，较大的数往后冒泡
for (int j = 0; j <array.length - i-1; j++) {
if (array[j] <array[j + 1]) {
//交换相邻两个数
temp=array[j];
array[j]=array[j+1];
array[j+1]=temp;
}
}
}
} else {
System.out.println("您输入的排序类型错误！");
}
}
/** 直接选择排序法----选择排序的一种
* 方法：每一趟从待排序的数据元素中选出最小（或最大）的一个元素，
*顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。*/
public static void selectSort(int[] array, String sortType) {
int temp,index;
if (sortType.equals("asc")) { //正排序，从小排到大
for (int i = 0; i < array.length; i++) {
index = i;//这里不是index=0
for (int j = i+1; j <array.length; j++)
if (array[index]>array[j])
index = j;
if(index!=i)
{
temp=array[i];
array[i]=array[index];
array[index]=temp;
}
}
} else if (sortType.equals("desc")) { //倒排序，从大排到小
for (int i = 0; i <array.length; i++) {
index = i;//这里不是index=0
for (int j =i+1;j <array.length; j++)
if (array[index]<array[j])
index = j;
//交换在位置i和index(最大值)两个数
if(index!=i)
{
temp=array[i];
array[i]=array[index];
array[index]=temp;
}
}
} else {
System.out.println("您输入的排序类型错误！");
}
}
/**
* 插入排序
* 方法：将一个记录插入到已排好序的有序表（有可能是空表）中,从而得到一个新的记录数增1的有序表。 * 性能：比较次数O(n^2),n^2/4
*比较次数是前两者的一般，而复制所需的CPU时间较交换少，所以性能上比冒泡排序提高一倍多，而比选择排序也要快。
*/
public static void insertSort(int[] array, String sortType) {
int insertValue;
if (sortType.equals("asc")) { //正排序，从小排到大
//比较的轮数
for (int i = 1; i <array.length; i++) {
//保证前i个数排好序
insertValue=array[i];
int index=i-1;
while(index>=0&&array[index]>insertValue)
{
array[index+1]=array[index];
index--;
}
array[index+1]=insertValue;
}
}
else if (sortType.equals("desc")) { //倒排序，从大排到小
//比较的轮数
for (int i = 1; i <array.length; i++) {
//保证前i个数排好序
insertValue=array[i];
int index=i-1;
while(index>=0&&array[index]<insertValue)
{
array[index+1]=array[index];
index--;
}
array[index+1]=insertValue;
}
} else
System.out.println("您输入的排序类型错误！");
}
/**
* 快速排序 快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）。 步骤为：
* 1. 从数列中挑出一个元素，称为 "基准"（pivot）， 2.
* 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分割之后，该基准是它的最后位置。这个称为分割（partition）操作。
* 3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
* 递回的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递回下去，但是这个算法总会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。 * * @param data
* 待排序的数组 */
public static void quickSort(int[] array, String sortType) {
if (sortType.equals("asc")) { // 正排序，从小排到大
qsort_asc(array, 0, array.length - 1); }
else if (sortType.equals("desc")) { // 倒排序，从大排到小
qsort_desc(array,0,array.length-1);
} else {
System.out.println("您输入的排序类型错误！");
}
}
/**
* 快速排序的具体实现，排正序
*/
public static void qsort_asc(int[] array, int left, int right) {
int i, j,pivot;
if (left < right) { // 这个条件用来结束递归
i = left;
j = right;
pivot= array[i];
while (i < j) {
while (i < j && array[j]>pivot)
j--; // 从右向左找第一个小于pivot的数
if (i < j) {
array[i] = array[j];
i++;
}
while (i < j &&array[i]<pivot)
i++; // 从左向右找第一个大于pivot的数
if (i < j) {
array[j] = array[i];
j--;
}
}
array[i] =pivot;
qsort_asc(array, left, i - 1);
qsort_asc(array, i + 1, right);
}
}
/**
* 快速排序的具体实现，排倒序
*/
public static void qsort_desc(int[] array, int left, int right) {
int i, j,pivot;
if (left < right) { // 这个条件用来结束递归
i = left;
j = right;
pivot= array[i];
while (i < j) {
while (i < j && array[j]<pivot)
j--; // 从右向左找第一个大于pivot的数
if (i < j) {
array[i] = array[j];
i++;
}
while (i < j &&array[i]>pivot)
i++; // 从左向右找第一个小于pivot的数
if (i < j) {
array[j] = array[i];
j--;
}
}
array[i] =pivot;
qsort_desc(array, left, i - 1);
qsort_desc(array, i + 1, right);
}
}
public static void main(String[] args) {
int[] arr1=createArray();
System.out.println("==========冒泡排序后(正序)==========");
bubbleSort(arr1, "asc");
OutputArray(arr1);
System.out.println("==========冒泡排序后(倒序)==========");
bubbleSort(arr1, "desc");
OutputArray(arr1);
int[] arr2=createArray();
System.out.println("==========选择排序后(正序)==========");
selectSort(arr2, "asc");
OutputArray(arr2);
System.out.println("==========选择排序后(倒序)==========");
selectSort(arr2, "desc");
OutputArray(arr2);
int[] arr3=createArray();
System.out.println("==========插入排序后(正序)==========");
insertSort(arr3, "asc");
OutputArray(arr3);
System.out.println("==========插入排序后(倒序)==========");
insertSort(arr3, "desc");
OutputArray(arr3);
int[] arr4=createArray();
System.out.println("==========快速排序后(正序)==========");
quickSort(arr4, "asc");
OutputArray(arr4);
System.out.println("==========快速排序后(倒序)==========");
quickSort(arr4, "desc");
OutputArray(arr4);
}
}
双向冒泡排序
import java.util.Random;
/**
* @author George
* @date:2011-2-3 17:08:51
*/
public class BubbleSort {
public static void OutputArray(int[] array) {
for (int data : array) {
System.out.print(data + " ");
}
System.out.println();
}
public static int[] createArray(int n) {
int array[] = new int[n];
Random r = new Random();
for (int i = 0; i < n; i++) {
array[i] = r.nextInt(100);
}
System.out.println("==========原始数组===========");
OutputArray(array);
return array;
}
public static void bubble(int[] array){
int i,start=0,end=array.length-1,temp;
boolean flag=true;
while(start<end&&flag)
{
flag=false;
for(i=start;i<end;i++)//从上往下冒泡
{
if(array[i]>array[i+1])
{
temp=array[i];
array[i]=array[i+1];
array[i+1]=temp;
flag=true;//表示交换
}
}
end--;
for(i=end;i>start;i--)
{
if(array[i]<array[i-1])
{
temp=array[i];
array[i]=array[i-1];
array[i-1]=temp;
flag=true;//表示交换
}
}
start++;
}
}
public static void main(String[] args) {
int arr[]=createArray(10);
bubble(arr);
System.out.println("==========排序后数组===========");
OutputArray(arr);
}
}
import java.util.Random;
/**
* @author George
* @date:2011-2-5 18:42:10
*/
public class Sort {
public static void OutputArray(int[] array) {
for (int data : array) {
System.out.print(data + " ");
}
System.out.println();
}
public static int[] createArray(int n) {
int array[] = new int[n];
Random r = new Random();
for (int i = 0; i < n; i++) {
array[i] = r.nextInt(100);
}
System.out.println("==========原始数组===========");
OutputArray(array);
return array;
}
private static int[] merge_sort(int[] array, int start, int end){
int[] result = new int[end-start+1];
if(start<end){
int mid= (start+end)/2;
int[] left= merge_sort(array, start, mid);
int[] right = merge_sort(array, mid+1, end);
result= merge(left,right);
} else if (start == end) {
result[0] = array[start];
return result;
}
return result;
}
private static int[] merge(int[] left, int[] right) {
int[] result = new int[left.length+right.length];
int i=0;
int j=0;
int k=0;
while(i<left.length&&j<right.length){
if(left[i]<right[j]){
result[k++] = left[i++];
}else{
result[k++] = right[j++];
}
}
while(i<left.length){
result[k++] = left[i++];
}
while (j<right.length) {
result[k++]= right[j++];
}
return result;
}
public static void main(String[] args) {
int arr[]=createArray(10);
int[] result = merge_sort(arr, 0, arr.length-1);
System.out.println("==========排序后数组===========");
OutputArray(result);
}
}
评论