最近在学习算法的一些知识,发现这些知识并非可有可无,不再做一个只会使用API的程序员,这是一个漫长的学习过程。
以下为常用的几个算法的Java实现,写在一个Junit测试类中了,这样方便执行,也不至于文件太多。
package alg;
import java.util.Arrays;
import org.junit.Test;
public class Algorithm {
private static long arr[] = new long[10];
static {
for (int i = 0; i < arr.length; i++) {
arr[i] = (long) (Math.random() * 100);
}
}
private void swap(long[] array, int i, int j) {
if (i == j) {
return;
}
long temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
@Test
public void arraysSort() {
System.out.println("排序前:" + Arrays.toString(arr));
Arrays.sort(arr);
System.out.println("排序后:" + Arrays.toString(arr));
}
/**
*
* 冒泡排序----交换排序的一种 方法:相邻两元素进行比较,如有需要则进行交换,每完成一次循环就将最大元素排在最后(如从小到大排序),
* 下一次循环是将其他的数进行类似操作。 性能:比较次数O(n^2),n^2/2;交换次数O(n^2),n^2/4
*
*/
@Test
public void bubbleSort() {
System.out.println("排序前:" + Arrays.toString(arr));
for (int i = arr.length - 1; i >= 1; i--) {
for (int j = 0; j < i; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1);
}
}
}
System.out.println("排序后:" + Arrays.toString(arr));
}
// 换一下泡泡的走向
@Test
public void bubbleSort2() {
System.out.println("排序前:" + Arrays.toString(arr));
for (int i = arr.length - 1; i >= 1; i--) {
for (int j = i; j > 0; j--) {
if (arr[j] < arr[j - 1]) {
swap(arr, j, j - 1);
}
}
}
System.out.println("排序后:" + Arrays.toString(arr));
}
/**
*
* 直接选择排序法----选择排序的一种 方法:每一趟从待排序的数据元素中选出最小(或最大)的一个元素,
* 顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完。 性能:比较次数O(n^2),n^2/2 交换次数O(n),n
* 交换次数比冒泡排序少多了,由于交换所需CPU时间比比较所需的CUP时间多,所以选择排序比冒泡排序快。
* 但是N比较大时,比较所需的CPU时间占主要地位,所以这时的性能和冒泡排序差不太多,但毫无疑问肯定要快些。
*/
@Test
public void selectSort() {
System.out.println("排序前:" + Arrays.toString(arr));
for (int i = 0; i < arr.length - 1; i++) {
int index = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[index] > arr[j]) {
index = j;
}
}
swap(arr, i, index);
}
System.out.println("排序后:" + Arrays.toString(arr));
}
/**
* 插入排序 方法:将一个记录插入到已排好序的有序表(有可能是空表)中,从而得到一个新的记录数增1的有序表。 性能:比较次数O(n^2),n^2/4
* 复制次数O(n),n^2/4 比较次数是前两者的一般,而复制所需的CPU时间较交换少,所以性能上比冒泡排序提高一倍多,而比选择排序也要快。
*/
@Test
public void insertSort() {
System.out.println("排序前:" + Arrays.toString(arr));
for (int i = 1; i < arr.length; i++) {
long temp = arr[i];
int j;
for (j = i; j > 0; j--) {
if (temp < arr[j - 1]) {
arr[j] = arr[j - 1];
} else {
break;
}
}
arr[j] = temp;
}
System.out.println("排序后:" + Arrays.toString(arr));
}
//来自于java.util.Arrays的源码
@Test
public void insertSort2() {
System.out.println("排序前:" + Arrays.toString(arr));
for (int i = 0; i < arr.length; i++) {
for (int j = i; j > 0 && arr[j - 1] > arr[j]; j--) {
swap(arr, j, j - 1);
}
}
System.out.println("排序后:" + Arrays.toString(arr));
}
@Test
public void quickSort() {
System.out.println("排序前:" + Arrays.toString(arr));
qSort(arr, 0, arr.length - 1);
System.out.println("排序后:" + Arrays.toString(arr));
}
private void qSort(long[] array, int low, int high) {
if (low < high) {
int pivot = partition(array, low, high);
qSort(arr, low, pivot - 1);
qSort(arr, pivot + 1, high);
}
}
private int partition(long[] array, int low, int high) {
long pivot = array[low];
int left = low;
int right = high;
while (left < right) {
while (array[left] <= pivot && left < right) {
left++;
}
while (array[right] > pivot) {
right--;
}
if (left < right) {
swap(array, left, right);
}
}
swap(array, low, right);
return right;
}
}
找到一个参考网址http://www.cs.princeton.edu/introcs/40algorithms/
分享到:
相关推荐
最快的排序算法 C语言最简单的排序算法冒泡排序并返回排序前索引序号,排序算法数据结构
最快的排序算法 最快的内部排序法—桶排序法,排序算法数据结构
最快的排序算法 最快的内部排序法—桶排序法 (1),排序算法数据结构
合并排序算法和快速排序算法采用了采用分治法、递归的方法,将时间复杂度降为O(nlogn)。在本次实验中将数据量提到5万的时候,该类算法运行时间仍在几毫秒左右,而上面的3种算法运行时间已经到达十几秒左右,效率...
该程序包含7大排序算法: # sort.bubbleSort() #冒泡排序 # sort.shellSort() #希尔排序 # sort.insertionSort() #插入排序 # sort.Selectionsort1() #选择排序 # sort.heapSort() #堆排序 # sort.countSort() ...
之前说过轴的选择是快速排序法的效率关键之一,在这边的快速排序法的轴选择方式更加快了快速排序法的效率,它是来自演算法名书 Introduction to Algorithms 之中。
常用排序算法的动态演示系统的开发,演示冒泡排序法、快速排序法、直接插入排序法、折半插入排序法、树形选择排序法
常见经典排序算法(C语言)1希尔排序 二分插入法 直接插入法 带哨兵的直接排序法 冒泡排序 选择排序 快速排序 堆排序.docx
总结了各种排序算法,并用C++代码实现,并有演示
桶式排序法桶式排序法桶式排序法桶式排序法
js排序算法动态显示js排序算法动态显示js排序算法动态显示js排序算法动态显示js排序算法动态显示js排序算法动态显示js排序算法动态显示js排序算法动态显示js排序算法动态显示js排序算法动态显示js排序算法动态显示js...
题目一: 内排序算法比较 1) 对以下6种常用的内部排序算法进行比较:起泡排序,直接插入排序,简单选择排序,快速排序,希尔排序,堆排序。 2) 待排序记录的文件个数不小于1000( 其数据用伪随机数产生),至少用5组...
十大经典排序算法 排序算法是《数据结构与算法》中最基本的算法之一。 排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中 进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序 记录,在...
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
1、本演示程序对以下6种常用的内部排序算法进行实测比较:起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序。 2、待排序表的表的元素的关键字为整数,表长不小于100;其中的数据要用伪随机数产生...
常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结
在STM8S003单片机上实现数组排序,用3种冒泡排序法对数组进行排序,并通过串口打印排序过程。
1、常见排序算法实现(1-6选择几个算法练习) 1)问题描述:输入一组关键字序列分别实现下列排序。 (1)实现简单选择排序、直接插入排序和冒泡排序。 (2)实现希尔排序算法。 (3)实现折半插入排序。 ...
使用简单数组实现下面各种排序算法的功能,并进行比较, 排序算法如下: a) 插入排序; b) 希尔排序; c) 冒泡排序; d) 快速排序; e) 简单选择排序; f) 堆排序; g) 归并排序; h) 基数排序(选作); i) 其他; ...
在之前所介绍过的排序方法,都是属于「比较性」的排序法,也就是每次排序时 ,都是比较整个键值的大小以进行排序。 这边所要介绍的「基数排序法」(radix sort)则是属于「分配式排序」(distribution sort),基数...