Java算法与数据结构 算法 排序算法 快速排序 冒泡排序 选择排序 合并排序 插入
Posted onJava算法与数据结构 算法 排序算法 快速排序 冒泡排序 选择排序 合并排序 插入排序 数据结构 单向链表 栈
Java算法与数据结构**
算法
排序算法
数据结构
快速排序**
博客分类:
交换排序法->快速排序 快速排序使用分治法策略来把一个序列分为两个子序列 算法步骤:
- 从数列中挑出一个元素,称为 "基准"(pivot)
- 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面 (相同的数可以到任一边)。在这个分割结束之后,该基准就处于数列的中间位置。这个称为分割(partition)操作
递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序 / 比较复杂度:O(n㏒n) / 交换(赋值)复杂度:O(n㏒n) /* 优点:比一般的排序都要快 Java代码
public static void quickSort(Integer[] array) {
- if (array == null || array.length== 0) {
- return;
- }
- quickSort(array,0,array.length-1);
- }
- private static void quickSort(Integer[] array, final int start, final int end){
- //数组长度<=1退出
- if(start>=end){
- return;
- }
- //数组长度==2,比较两个元素的大小
- if(end-start==1){
- if(array[start]>array[end]){
- swap(array,start,end);
- }
- return;
- }
- //用来进行比较的数
- int compareNumber = array[start];
- int middlePosition = 0;
- int i = start;
- int j = end;
- for(;;i++,j--){
- //从数组首端开始迭代(不包括compareNumber),如果数组的数<compareNumber,不做移动
- while(array[i]<compareNumber&&i<j){
- i++;
- }
- //从数组尾端迭代,如果数组的数>=compareNumber,不做移动
- while(array[j]>compareNumber&&i<j){
- j--;
- }
- if(i>=j){
- if(array[j]>compareNumber){
- middlePosition = j;
- }else{
- middlePosition = (j+1);
- }
- break;
- }
- //从数组首端开始迭代,得到大于compareNumber的数array[i],此时从尾端迭代直至得到<=compareNumber的数
- //array[j],交换这两个数的位置,然后继续迭代
- swap(array,i,j);
- }
- //递归排序
- quickSort(array,start,middlePosition-1);
- quickSort(array,middlePosition,end);
- }
- public static void swap(Object[] array,int a,int b){
- Object temp = array[a];
- array[a] = array[b];
- array[b] = temp;
- }
冒泡排序**
博客分类:
交换排序->冒泡排序 算法步骤:
- 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
- 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。
- 针对所有的元素重复以上的步骤,除了最后一个。
public static void bubbleSort(Integer[] array){
- for(int i=array.length-1;i>=0;i--){
- for(int j=0;j<i;j++){
- if(array[j]>array[j+1]){
- swap(array, j, j+1);
- }
- }
- }
public static void swap(Object[] array,int a,int b){
- Object temp = array[a];
- array[a] = array[b];
- array[b] = temp;
- }
来源: [http://tangyanbo.iteye.com/blog/1470870](http://tangyanbo.iteye.com/blog/1470870)选择排序**
博客分类:
选择排序法->选择排序 算法步骤:
- 未排序序列中找到最小元素,存放到排序序列的起始位置
- 再从剩余未排序元素中继续寻找最小元素,然后放到排序序列末尾
以此类推,直到所有元素均排序完毕 比较复杂度:n(n-1)/2 交换(赋值)复杂度:n-1 优点:相比冒泡排序来讲,交换的次数减少了 缺点:相对快速排序,比较次数仍然是n² Java代码
public static void selectionSort(Integer[] array){
- for(int i=0;i<array.length-1;i++){
- //最小数存放位置
- int minPosition = i;
- for(int j=i+1;j<array.length;j++){
- if(array[j]<array[minPosition]){
- //新的最小数位置
- minPosition = j;
- }
- }
- //找到剩余元素中的最小数,并将其交换至起始位置
- swap(array, i, minPosition);
- }
public static void swap(Object[] array,int a,int b){
- Object temp = array[a];
- array[a] = array[b];
- array[b] = temp;
- }
来源: [http://tangyanbo.iteye.com/blog/1470871](http://tangyanbo.iteye.com/blog/1470871)插入排序**
博客分类:
插入排序 算法步骤: 1.从第一个元素开始,该元素可以认为已经被排序 2.取出下一个元素a,在已经排序的元素序列中从后向前扫描 3.如果已排序中的元素b大于a,则将元素b后移一个位置 4.重复步骤3,直到找到已排序的元素x小于或者等于元素a 5.将元素a插入到x的后面 6.重复步骤2~5 Java代码
- public static void insertionSort(Integer[] array){
- for(int i=1;i<array.length;i++){
- //待插入的数据
- Integer toBeInsertedValue = array[i];
- int j;
- for(j=i;j>0;j--){
- if(array[j-1]>toBeInsertedValue){
- //将比toBeInsertedValue大的元素全部后移
- array[j]=array[j-1];
- continue;
- }
- break;
- }
- //插入新元素
- array[j]=toBeInsertedValue;
- }
- }
来源: [http://tangyanbo.iteye.com/blog/1472367](http://tangyanbo.iteye.com/blog/1472367)