Java排序分类为:
* 1.插入排序(直接插入排序、折半插入排序、希尔排序);
* 2.交换排序(冒泡排序、快速排序);
* 3.选择排序(直接选择排序、堆排序);
* 4.归并排序;
* 5.基数排序。
下面实现代码为:
- /*
- * To change this template, choose Tools | Templates
- * and open the template in the editor.
- */
- package com.xiva.baseKnowledge;
- import java.util.Arrays;
- import java.util.LinkedList;
- import java.util.List;
- /**
- * 1.插入排序(直接插入排序、折半插入排序、希尔排序);
- * 2.交换排序(冒泡排序、快速排序);
- * 3.选择排序(直接选择排序、堆排序);
- * 4.归并排序;
- * 5.基数排序。
- * @author XIVA
- */
- public class SortPractice <T extends Comparable> {
- /**
- * 直接插入排序
- * @Description 在要排序的一组数中,假设前面(n-1) [n>=2] 个数已经是排
- 好顺序的,现在要把第n个数插到前面的有序数中,使得这n个数
- 也是排好顺序的。如此反复循环,直到全部排好顺序
- * @param array needing to sort
- * @param direction of sorting, 0 represent desc, 1 represent asc, others don't sorting.
- */
- public void directInsertSort(T[] array, int direction){
- //升序
- if( direction == 1){
- for(int i=0; i< array.length; i++){
- for(int j=0; j< i; j ++){
- if( array[i].compareTo(array[j]) < 0 ){
- T temp = array[i];
- //后移一位
- for( int k = i; k > j; k--){
- array[k] = array[k-1];
- }
- array[j] = temp;
- break;
- }
- }
- }
- }
- //降序
- if( direction == 0){
- for( int i=0; i< array.length; i++ ){
- for(int j=0; j< i; j ++){
- if( array[i].compareTo(array[j]) > 0 ){
- T temp = array[i];
- //后移一位
- for( int k = i; k > j; k--){
- array[k] = array[k-1];
- }
- array[j] = temp;
- break;
- }
- }
- }
- }
- }
- /**
- * 折半插入排序
- * 当第i个数插入时,前面i-i个数都已经排好序了,我们没有必要从第一个数开始比较大小;
- * 我们可以从第(i-i)/2个数开始比较大小,
- * @param array
- * @param direction
- */
- public void binaryInsertSort(T[] array, int direction){
- int index, position, low, high = 0;
- T temp;
- //升序
- if( direction == 1){
- for(int i = 1; i< array.length; i++){
- low = 0;
- high = i - 1;
- temp = array[i];
- while(low <= high){
- index = (low + high) >> 1;
- if( array[i].compareTo(array[index]) > 0 ){
- low = index + 1;
- }else if( array[i].compareTo(array[index]) < 0 ){
- high = index - 1;
- }else{
- break;
- }
- }
- position = i;
- while(position > low){
- array[position] = array[position-1];
- position--;
- }
- array[low] = temp;
- }
- }
- }
- /**
- * 希尔排序
- * 先取一个正整数d1小于n,把所有序号相隔d1的数组元素放一组,组内进行直接插入排序;
- * 然后取d2小于d1,重复上述分组和排序操作;直至di=1,即所有记录放进一个组中排序为止
- * @Description
- * @param array 需要排序数组
- * @param direction 0 desc,1 asc;
- */
- public void shellSort(T[] array, int direction){
- int len = array.length;
- int jump = len;
- T temp;
- while( jump > 1){
- jump = jump >> 1;
- for(int i = 0; i < jump; i++){
- //下面属于直接插入排序
- for( int j = i; j < len; j = j + jump){
- for(int k = i; k < j; k = k + jump){
- if( direction == 1 ){
- if( array[j].compareTo(array[k]) < 0 ){
- temp = array[k];
- array[k] = array[j];
- array[j] = temp;
- }
- }
- else{
- if( array[j].compareTo(array[k]) > 0 ){
- temp = array[k];
- array[k] = array[j];
- array[j] = temp;
- }
- }
- }
- }
- }
- }
- }
- /**
- * 冒泡排序
- * 依次比较相邻的两个数,将小数放在前面,大数放在后面。即在第一趟:首先比较第1个和第2个数,将小数放前,大数放后。
- * 然后比较第2个数和第3个数,将小数放前,大数放后,如此继续,直至比较最后两个数,将小数放前,大数放后。
- * 至此第一趟结束,将最大的数放到了最后。
- * 在第二趟:仍从第一对数开始比较(因为可能由于第2个数和第3个数的交换,使得第1个数不再小于第2个数),
- * 将小数放前,大数放后,一直比较到倒数第二个数(倒数第一的位置上已经是最大的),
- * 第二趟结束,在倒数第二的位置上得到一个新的最大数(其实在整个数列中是第二大的数)。
- * 如此下去,重复以上过程,直至最终完成排序。
- * @param array
- * @param direction
- */
- public void bubbleSort( T[] array, int direction ){
- int len = array.length;
- T temp;
- for( int i=0; i < len; i++ ){
- for(int j = i; j < len - 1; j++ ){
- if ( direction == 1 ){
- if( array[i].compareTo(array[j + 1]) > 0){
- temp = array[i];
- array[i] = array[j + 1];
- array[j + 1] = temp;
- }
- }else if( direction == 0 ){
- if( array[i].compareTo(array[j + 1]) < 0){
- temp = array[i];
- array[i] = array[j + 1];
- array[j + 1] = temp;
- }
- }
- }
- }
- }
- /**
- * 快速排序
- * @Description 通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,
- * 然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
- * @param array
- * @param direction , int i, int j, int direction
- */
- public void quickSort( T[] array, int start, int end ){
- int keyIndex = start;
- int compIndex = end;
- T temp;
- if( end <= start){
- return;
- }
- while(true){
- if( compIndex == keyIndex ){
- break;
- }
- if( array[keyIndex].compareTo(array[compIndex] ) > 0 ){
- if( keyIndex < compIndex ){
- temp = array[keyIndex];
- array[keyIndex] = array[compIndex];
- array[compIndex] = temp;
- //交换keyIndex与compIndex的值
- keyIndex = keyIndex + compIndex;
- compIndex = keyIndex - compIndex + 1;
- keyIndex = keyIndex - compIndex + 1;
- }else{
- compIndex = compIndex + 1;
- }
- }else if( array[keyIndex].compareTo(array[compIndex]) < 0 ){
- if( keyIndex > compIndex ){
- temp = array[keyIndex];
- array[ keyIndex ] = array[ compIndex ];
- array[ compIndex] = temp;
- //交换keyIndex与compIndex的值
- keyIndex = keyIndex + compIndex;
- compIndex = keyIndex - compIndex - 1;
- keyIndex = keyIndex - compIndex - 1;
- }else{
- compIndex = compIndex - 1;
- }
- }else{
- if( keyIndex < compIndex ){
- //交换keyIndex与compIndex的值
- keyIndex = keyIndex + compIndex;
- compIndex = keyIndex - compIndex + 1;
- keyIndex = keyIndex - compIndex + 1;
- }else{
- //交换keyIndex与compIndex的值
- keyIndex = keyIndex + compIndex;
- compIndex = keyIndex - compIndex - 1;
- keyIndex = keyIndex - compIndex - 1;
- }
- }
- }
- //递归
- quickSort(array, start, keyIndex - 1 );
- quickSort(array, keyIndex + 1, end );
- }
- /**
- * @Description 直接选择排序
- * 和冒泡排序类似,莫要混淆了
- * 第一次从R[0]~R[n-1]中选取最小值,与R[0]交换,第二次从R{1}~R[n-1]中选取最小值,与R[1]交换,....,
- * 第i次从R[i-1]~R[n-1]中选取最小值,与R[i-1]交换,.....,第n-1次从R[n-2]~R[n-1]中选取最小值,与R[n-2]交换,
- * 总共通过n-1次,得到一个按排序码从小到大排列的有序序列.
- * 冒泡排序每一次比较都有可能交换值;这个需要记住每一趟最大值或者最小值的位置
- * @param array
- * @param direction
- */
- public void straightSelectSort(T[] array, int direction){
- int len = array.length;
- T mTempData;
- int change_index;
- for( int i = 0; i < len; i++ ){
- mTempData = array[i];
- change_index = i;
- for( int j = i; j < len; j++ ){
- if( mTempData.compareTo(array[j]) > 0){
- mTempData = array[j];
- change_index = j;//记住最大值的位置
- }
- }
- array[change_index] = array[i];
- array[i] = mTempData;
- }
- }
- /**
- * 最大堆
- * @param array
- * @param i
- */
- public void maxHeapify( T[] array, int i){
- int left = 2*i+1;
- int right = 2*i+2;
- int max = i;
- //先判断左子节点
- if( left < array.length && array[max].compareTo(array[left]) < 0 ){
- max = left;
- }
- //需要确定右子节点是否存在
- if( right < array.length && array[max].compareTo(array[right]) < 0 ){
- max = right;
- }
- if( max != i ){
- //System.out.println("swap");
- T tmp = array[max];
- array[max] = array[i];
- array[i] = tmp;
- maxHeapify(array, max);
- }
- }
- /**
- * 最小堆
- * @param array
- * @param i
- */
- public void minHeapify( T[] array, int i){
- int left = 2*i+1;
- int right = 2*i+2;
- int max = i;
- //先判断左子节点
- if( left < array.length && array[max].compareTo(array[left]) > 0 ){
- max = left;
- }
- //需要确定右子节点是否存在
- if( right < array.length && array[max].compareTo(array[right]) > 0 ){
- max = right;
- }
- if( max != i ){
- //System.out.println("swap");
- T tmp = array[max];
- array[max] = array[i];
- array[i] = tmp;
- minHeapify(array, max);
- }
- }
- /**
- * 创建堆
- * 堆从逻辑上讲是一种非线性结构,但实际中我们使用线性结构来存储;堆首先是一个完全二叉树,根节点的值是最大值(最小值)
- * @param array
- */
- public void createHeap( T[] array ){
- int len = (array.length-1)/2;
- for ( int i = len; i >= 0; i-- ){
- //maxHeapify(array, i);
- minHeapify(array, i);
- }
- }
- /**
- * 堆排序
- *
- * @param array
- * @param direction
- */
- public T[] heapSort(T[] array,T[] result, int direction){
- int index = 0;
- int len = array.length;
- //取出堆顶,重复建堆
- for ( int i = len-1; i >= 0; i-- ){
- result[index] = array[0];
- index++;
- array[0] = array[array.length-1];
- array = Arrays.copyOfRange(array, 0, i);
- minHeapify(array, 0);
- //maxHeapify(array, 0);
- }
- return result;
- }
- public void merge ( T[] array, int low, int mid, int high){
- //T[] tempArr = new Object<T>[high - low];
- List<T> tempList = new LinkedList<T>();
- int s1 = low;
- int s2 = mid + 1;
- while( s1 <= mid && s2 <= high ){
- if( array[s1].compareTo(array[s2]) <= 0){
- tempList.add(array[s1++]);
- }else{
- tempList.add(array[s2++]);
- }
- }
- if(s1 <= mid){
- for(int i=s1; i <= mid; i++){
- tempList.add(array[i]);
- }
- }
- if(s2 <= high){
- for(int i=s2; i <= high; i++){
- tempList.add(array[i]);
- }
- }
- Object[] arrayList = tempList.toArray();
- System.out.println(Arrays.toString(arrayList) + low + ":" + high);
- for (int i=0;i<arrayList.length;i++){
- array[low + i] = (T)arrayList[i];
- }
- tempList.clear();
- }
- /**
- * 归并排序
- * @param array
- * @param low
- * @param high
- */
- public void mergeSort( T[] array,int low, int high){
- //int len = array.length;
- if (low < high){
- mergeSort(array, low, (low + high)/2);
- mergeSort(array, (low + high)/2 + 1, high);
- merge(array, low, (low + high)/2, high);
- }
- }
- public static void main(String[] args){
- SortPractice sort = new SortPractice();
- Integer num01 = new Integer(12);
- Integer num02 = new Integer(13);
- Integer num03 = new Integer(44);
- Integer num04 = new Integer(3);
- Integer num05 = new Integer(13);
- Integer num06 = new Integer(5);
- Integer num07 = new Integer(7);
- Integer[] array = {num01, num02, num03, num04, num05, num06, num07, num04};
- //Integer[] result = new Integer[array.length];
- //sort.directInsertSort(array, 1);
- //sort.binaryInsertSort(array, 1);
- //sort.shellSort(array, 1);
- System.out.println(Arrays.toString(array));
- sort.mergeSort(array, 0, array.length - 1);
- //sort.bubbleSort(array, 1);
- //sort.quickSort(array, 0, array.length - 1);
- //sort.createHeap(array);
- System.out.println(Arrays.toString(array));
- //sort.heapSort(array, result, 1);
- //System.out.println(Arrays.toString(result));
- /*for( int i=0; i < array.length; i++ ){
- System.out.println( array[i] );
- }*/
- }
- }
还有基数排序未实现。
相关推荐
这个名为"Java各种排序算法代码.zip"的压缩包包含了一系列实现不同排序算法的Java源代码。排序算法是计算机科学中的基本概念,用于对一组数据进行排列。下面将详细讨论这些算法及其在Java中的实现。 1. 冒泡排序...
本文将详细介绍几种常见的Java排序算法,包括它们的工作机制、优缺点以及适用场景。 1. 插入排序 - 直接插入排序:该算法通过将每个元素插入到已排序部分的正确位置来工作。在Java中,可以通过遍历数组,将每个...
在编程领域,排序算法是数据结构与算法学习中的基础部分,尤其在Java中,了解和掌握各种排序算法对于提升程序性能至关重要。以下是对标题和描述中提到的Java各种排序算法的详细解释,以及它们的实现代码概述。 1)*...
Java作为广泛应用的编程语言,提供了丰富的工具和方法来实现各种排序算法。以下是对标题"java各种排序算法"和描述中涉及的知识点的详细说明。 1. **冒泡排序(Bubble Sort)** 冒泡排序是最基础的排序算法之一,通过...
本资料包"Java各种排序算法Demo"聚焦于通过Java代码展示不同的排序算法,旨在帮助开发者理解和应用这些算法。 首先,我们来探讨几种基础的排序算法: 1. **冒泡排序**:冒泡排序是一种简单的排序算法,通过重复...
以下是对"面试最常见的问题(java各种排序法)"这一主题的详细解释。 首先,我们来了解一下排序的基本定义:排序是将一组数据按照特定顺序进行排列的过程。在计算机科学中,这通常指的是对数组或列表等数据结构中的...
所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。...在各个领域中考虑到数据的各种限制和规范,要得到一个符合实际的优秀算法,得经过大量的推理和分析。
Java作为一种广泛使用的编程语言,提供了丰富的工具和方法来实现各种排序算法。本篇将详细讲解标题为"Java各种排序算法代码"的知识点,这些代码案例不仅完整,而且能够运行,非常适合学习和实践。 1. 冒泡排序...
在这个"Java各种排序算法、Java游戏和实例代码集合"中,我们可以深入学习Java编程的核心技术,并通过实践加强理解。以下是一些关键知识点的详细说明: 1. **排序算法**: - **冒泡排序**:是最基础的排序算法之一...
本资源"java各种排序算法源码"涵盖了六种常见的排序算法,它们分别是:直接插入排序、希尔排序、冒泡排序、快速排序、直接选择排序和堆排序。接下来,我们将详细探讨这些排序算法的基本原理、特点以及在Java中的实现...
这里,我们将深入探讨一些常见的Java排序算法,包括它们的工作原理、优缺点以及适用场景。 1. 冒泡排序(Bubble Sort): 冒泡排序是一种简单的交换排序,通过重复遍历数组,比较相邻元素并根据需要交换它们,直到...
java各种排序算法实现,仅供参考。java各种排序算法实现,仅供参考。
本文将深入探讨Java中的各种排序方法以及它们的改良策略。首先,我们来看看几种基础的排序算法,然后讨论如何通过优化来提高这些算法的性能。 1. **冒泡排序**(Bubble Sort): 冒泡排序是最基础的排序算法之一,...