- ===冒泡排序===
JAVA语言实现
/**
* 学习冒泡排序
* 冒泡排序(Bubble Sort,台湾译为:泡沫排序或气泡排序)是一种简单的排序算法。它重复地走访过要排序的数列,
* 一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,
* 也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
*
* 冒泡排序算法的运作如下:
* 1. 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
* 2. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。
* 3. 针对所有的元素重复以上的步骤,除了最后一个。
* 4. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
*
* 使用冒泡排序为一列数字进行排序的过程
* 分类 排序算法
* 数据结构 数组
* 最差时间复杂度 O(n^2)
* 最优时间复杂度 O(n)
* 平均时间复杂度 O(n^2)
* 最差空间复杂度 总共O(n),需要辅助空间O(1)
* 最佳算法 No
* @author Administrator
*
*/
public class Demos {
/**
* 自己编写的糟糕的冒泡排序算法
*/
protected void bubbleSort(int[] digits) {
long time1 = new Date().getTime();
int temp =0;
for(int j=0;j<digits.length-1;j++){// 要排序的轮数,数字个数减一(n-1)
for(int i=0;i<digits.length;i++){// 每一轮排序
if(i != digits.length -1 && digits[i] > digits[i+1]){// 第一个条件是为了防止arrayOutofIndex
temp = digits[i];
digits[i] = digits[i+1];
digits[i+1] = temp;
}
}
}
long time2 = new Date().getTime();
System.out.println("expended time: "+(time2-time1)+" ms");
// System.out.println("数据排序消耗的时间: "+(time2-time1)+"毫秒");
// 排好序后输出
for(int j=0;j<digits.length;j++){
System.out.print(digits[j]+",");
}
}
/** 维基百科上的JAVA冒泡排序,学习了!*/
protected void bubbleSort2(int[] digits){
long time1 = new Date().getTime();
int temp = 0;
for(int i= digits.length - 1;i > 0; --i){// 排序的轮数
for(int j=0;j<i;++j){// 每一轮排序。每轮过后要排序的数字减少一个,非常好。
if(digits[j] > digits[j+1]){
temp = digits[j];
digits[j] = digits[j+1];
digits[j+1] = temp;
}
}
}
long time2 = new Date().getTime();
// 输出排序消耗的时间
System.out.println("\nexpended time: "+(time2-time1)+" ms");
// 排好序后输出
for(int j=0;j<digits.length;j++){
System.out.print(digits[j]+",");
}
}
private int[] digits = {3,5,8,6,9,78,32,50,11,30}; // 待排序的数字
public static void main(String arg[]) throws IOException {
Demos demo = new Demos();
demo.bubbleSort(demo.digits); // test Bubble Sort
demo.bubbleSort2(demo.digits); // test Bubble Sort2
}
}
Java自我练习
public class Hello {
public static void main(String[] args) {
// System.out.println("Well done!");
//int[] data = {12,5,3,11,20,6,10,45,87,9,13,38};
//int[] data = {1,2,3,4,5,6,7,8,9,10};//最好的情况,1轮比较
int[] data = {10,9,8,7,6,5,4,3,2,1};//最糟糕的情况,n-1轮比较
bubble(data);
bubbleV2(data);
// for(int j=0;j<data.length;j++){
// boolean exchange = false;
// for(int i=0;i<data.length-1-j;i++){
// System.out.println("compare "+i+" with "+(i+1));
// if(data[i] > data[i+1]){
// exchange = true;
// int temp = data[i];
// data[i] = data[i+1];
// data[i+1] = temp;
// }
// }
//
// for(int i=0;i<data.length;i++){
// System.out.print(data[i]+" ");
// }
// System.out.println();
// if(!exchange){break;}
// }
}
private static void bubble(int[] data){
for(int j=0;j<data.length;j++){
for(int i=0;i<data.length-1;i++){
System.out.println("compare "+i+" with "+(i+1));
if(data[i] > data[i+1]){
int temp = data[i];
data[i] = data[i+1];
data[i+1] = temp;
}
}
for(int i=0;i<data.length;i++){
System.out.print(data[i]+" ");
}
System.out.println();
}
}
private static void bubbleV2(int[] data){
for(int j=0;j<data.length;j++){
boolean exchange = false;
for(int i=0;i<data.length-1;i++){
System.out.println("compare "+i+" with "+(i+1));
if(data[i] > data[i+1]){
exchange = true;
int temp = data[i];
data[i] = data[i+1];
data[i+1] = temp;
}
}
for(int i=0;i<data.length;i++){
System.out.print(data[i]+" ");
}
System.out.println();
if(!exchange){break;}
}
}
private static void bubbleV3(int[] data){
for(int j=0;j<data.length;j++){
boolean exchange = false;
for(int i=0;i<data.length-1-j;i++){
System.out.println("compare "+i+" with "+(i+1));
if(data[i] > data[i+1]){
exchange = true;
int temp = data[i];
data[i] = data[i+1];
data[i+1] = temp;
}
}
for(int i=0;i<data.length;i++){
System.out.print(data[i]+" ");
}
System.out.println();
if(!exchange){break;}
}
}
}
C语言实现
/* 冒泡排序C语言实现 */
#include <stdio.h>
/**/
void BubbleSort(int digits[],int count){
int temp = 0;
int i,j;
for(i=count-1;i>0;--i){
for(j=0;j<i;++j){
if(digits[j] > digits[j+1]){
temp = digits[j];
digits[j] = digits[j+1];
digits[j+1] = temp;
}
}
}
}
void main(){
int digits[] = {3,5,8,6,9,78,32,50,11,30};
int i;
/*clean early output*/
clrscr();
/*冒泡排序*/
BubbleSort(digits,10);
/*结果输出*/
for(i=0;i<10;++i){
printf("%4d",digits[i]);
}
/*when the user press the keyboard then exit*/
getch();
}
- ===快速排序===
C语言实现
#include "stdio.h"
#include "string.h"
#include "conio.h"
#include "windows.h"
//一趟快速排序
int Partition(int a[], int low, int high)
{
int pivotKey = a[low];//枢轴暂时取第一个数
//如果low位置比high位置小
while(low < high){
while(low<high && a[high]>=pivotKey) --high;//如果high位置数据比pivotKey大,则high向前移动一个位置
a[low] = a[high];
while(low<high && a[low]<pivotKey) ++low;//如果low位置数据比pivotKey小,则low向后移动一个位置
a[high] = a[low];
}
a[low] = pivotKey;
return low;
}
//输出一个数组
void printArray(int a[])
{
for(int i=0;i<10;i++)
{
printf("%d,",a[i]);
}
}
/***********************************************************
*
* Quick Sort快速排序(递归)
*
***********************************************************/
void Qsort(int a[],int low,int high)
{
if(low < high)
{
int loc = Partition(a,low,high);
Qsort(a,low,loc-1);
Qsort(a,loc+1,high);
}
}
/***********************************************************
*
* main() function
*
***********************************************************/
void main()
{
printf("Hello World\n");
//
//int a[10]={8,1,4,9,6,3,5,2,7,0};
int a[10]={49,38,65,97,76,13,27,49,25,50};
//DWORD dwStart = GetTickCount();计算程序的运行时间
Qsort(a,0,9);
//DWORD dwEnd = GetTickCount();
//printf("run time- %d\n",(dwEnd-dwStart));
printArray(a);
getch();//接收一次用户按键再exit程序
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)