12°

常用排序算法

/**  
 * <p>All rights Reserved, Designed By <b>CISCO</b></p>
 * @Title:  <b>TestAlogr.java</b>   
 * @Package com.example.demo   
 * @Description:    TODO   
 * @author: Jacky Dong     
 * @date:   Jan 14, 2020 2:13:00 PM   
 * @version V1.0 
 * @Copyright: 2020 www.cisco.com Inc. All rights reserved. 
 * 
 */
package com.example.demo;

import java.util.ArrayList; import java.util.List;

import org.junit.Test;

/**

  • @ClassName: TestAlogr

  • @Description: TODO

  • @author: Jacky Dong

  • @date: Jan 14, 2020 2:13:00 PM

  • @since 1.8

  • @Copyright: <b>2020 cisco.com Inc. All rights reserved. </b> */ public class TestAlogr {

    @Test public void testBucket() { ArrayList<Integer> arrs = new ArrayList<Integer>(); arrs.add(2); arrs.add(0); arrs.add(8); arrs.add(5); arrs.add(3); arrs.add(4); arrs.add(7); arrs.add(9); arrs.add(1); List<Integer> newArrayIntegers = blucketSort(arrs , 2);

     for(int i = 0 ; i &lt; newArrayIntegers.size() ; i++) {
     	System.out.println(newArrayIntegers.get(i));
     }
    

    }

    public List<Integer> blucketSort(List<Integer> arrs, int bulcketSize) {

     if(arrs.isEmpty() || arrs.size()&lt;2) {
     	return arrs;
     }
     int max = 0;
     int min = 0;
     ArrayList&lt;Integer&gt; resultArr = new ArrayList&lt;&gt;();
    
    
     for(int i = 0 ; i &lt; arrs.size() ; i++) {
     	if(arrs.get(i)&gt;max) {
     		max = arrs.get(i);
     	}
    
     	if(arrs.get(i)&lt;min) {
     		min = arrs.get(i);
     	}
     }
    
     int bulcketCount = (max-min/bulcketSize) +1;
    
    
     System.out.println("bulcketCount : "+bulcketCount);
     List&lt;List&lt;Integer&gt;&gt; bulcket = new ArrayList&lt;List&lt;Integer&gt;&gt;();
    
    
     for(int i = 0 ; i &lt; bulcketCount ; i++) {
     	bulcket.add(new ArrayList&lt;Integer&gt;());
     }
    
     //将数据添加到具体的桶中
     for(int i = 0 ; i &lt; arrs.size() ; i++) {
     	bulcket.get(arrs.get(i)-min/bulcketSize).add(arrs.get(i));
     }
    
     for(int i = 0 ; i &lt; bulcketCount ; i++) {
     	if(bulcketSize ==1) {
     		for(int j = 0 ; j &lt; bulcket.get(i).size() ;j++) {
     			resultArr.add(bulcket.get(i).get(j));
     		}
     	}else {
     		if(bulcketCount ==1) {
     			bulcketSize--;
     		}
    
     		 List&lt;Integer&gt; temp = blucketSort(bulcket.get(i), bulcketSize);
    
             for (int j = 0; j &lt; temp.size(); j++)
                 resultArr.add(temp.get(j));				
     	}
     }
     return resultArr;
    

    }

}

 

 

 

/**  
 * <p>All rights Reserved, Designed By <b>CISCO</b></p>
 * @Title:  <b>TestQuickSort.java</b>   
 * @Package com.example.demo   
 * @Description:    TODO   
 * @author: Jacky Dong     
 * @date:   Jan 13, 2020 8:27:07 PM   
 * @version V1.0 
 * @Copyright: 2020 www.cisco.com Inc. All rights reserved. 
 * 
 */
package com.example.demo;

import java.util.Arrays;

/**

  • @ClassName: TestQuickSort

  • @Description: TODO

  • @author: Jacky Dong

  • @date: Jan 13, 2020 8:27:07 PM

  • @since 1.8

  • @Copyright: <b>2020 cisco.com Inc. All rights reserved. </b> */ public class TestQuickSort {

    public static void main(String[] args) { int[] arrs = {2 ,0 ,8 ,3 ,11 ,1 ,9 ,4 ,7};

     quickSort(arrs , 0 , arrs.length-1);
    

// for(int i = 0 ; i < arrs.length ; i++) { // System.out.println(arrs[i]); // } }

private static void quickSort(int[] arrs , int start ,int end) {
	
	System.out.println(Arrays.toString(arrs));
	if(arrs.length &lt;= 1||start &gt;= end) {
		return;
	}
	
	int partitionIndex = partition(arrs , start , end);

	//左边画一个龙
	quickSort(arrs,start,partitionIndex-1);
	//右边画一个彩虹
	quickSort(arrs,partitionIndex+1,end);
	
}


private static int partition(int[] array , int start ,int end) {
	//定义一个基准点,我以最后一个为基准点
	int privot = array[end];
	int privotIndex = start;
	
	for(int i = start ; i &lt; end ; i++) {
		if(privot &gt; array[i]) {
			if(i &gt;= privotIndex) {
				swap(array , i , privotIndex);
				privotIndex++;
			}
		}
	}
	
	swap(array , privotIndex , end);
	return privotIndex;
}


private static void swap(int[] array , int positioni , int positionj) {
	int tmp = array[positioni];
	array[positioni] = array[positionj];
	array[positionj] = tmp;
}

}

 

 

/**  
 * <p>All rights Reserved, Designed By <b>CISCO</b></p>
 * @Title:  <b>TestStack.java</b>   
 * @Package com.example.demo   
 * @Description:    TODO   
 * @author: Jacky Dong     
 * @date:   Jan 13, 2020 11:38:19 AM   
 * @version V1.0 
 * @Copyright: 2020 www.cisco.com Inc. All rights reserved. 
 * 
 */
package com.example.demo;

import java.util.Stack;

/**

  • @ClassName: TestStack
  • @Description: TODO
  • @author: Jacky Dong
  • @date: Jan 13, 2020 11:38:19 AM
  • @since 1.8
  • @Copyright: <b>2020 cisco.com Inc. All rights reserved. </b> */

public class TestStack{

	public static void main(String[] args) {
		ListNode l1 = new ListNode(7);
		l1.next= new ListNode(2);
		l1.next.next= new ListNode(4);
		l1.next.next.next = new ListNode(3);
		
		ListNode l2 = new ListNode(5);
		l2.next= new ListNode(6);
		l2.next.next= new ListNode(4);
		ListNode l3 = addTwoNumbers(l1,l2);
		System.out.println(l3);
		
	}
	public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
		Stack&lt;Integer&gt; stack1 = new Stack&lt;Integer&gt;();
		Stack&lt;Integer&gt; stack2 = new Stack&lt;Integer&gt;();

		
		ListNode head = null;
		while (l1!=null) {
			stack1.push(l1.val);
			l1 = l1.next;
		}
		
		
		while(l2!=null) {
			stack2.push(l2.val);
			l2 = l2.next;
		}
		
		int result =0 ;
		int carry = 0;
		
		ListNode curr = null;
		ListNode prev = null;
		while (!stack1.isEmpty() ||!stack2.isEmpty()) {
			
			if(stack1.isEmpty() &amp;&amp; !stack2.isEmpty()) {
				result = stack2.pop();
			}else if (!stack1.isEmpty() &amp;&amp; stack2.isEmpty()) {
				result = stack1.pop();
			}else {
				result = stack1.pop()+stack2.pop();
			}
			
			result = result == 0 ? 0: (carry + result) ;
			
			carry = result / 10;
			
			curr = new ListNode(result%10);
			curr.next = prev;
			prev = curr;

// stack3.push(result%10);

			System.out.println(result%10);
			
		}
		
		return curr;
		
	}
	


}

class ListNode {
	int val;
	ListNode next;

	ListNode(int x) {
		val = x;
	}
}

 

/**  
 * <p>All rights Reserved, Designed By <b>CISCO</b></p>
 * @Title:  <b>TestSort.java</b>   
 * @Package com.example.demo   
 * @Description:    TODO   
 * @author: Jacky Dong     
 * @date:   Jan 12, 2020 12:57:44 PM   
 * @version V1.0 
 * @Copyright: 2020 www.cisco.com Inc. All rights reserved. 
 * 
 */
package com.example.demo;

import org.junit.Test;

/**

  • @ClassName: TestSort
  • @Description: TODO
  • @author: Jacky Dong
  • @date: Jan 12, 2020 12:57:44 PM
  • @since 1.8
  • @Copyright: <b>2020 cisco.com Inc. All rights reserved. </b> */

public class TestSort {

/**   
 * @Title: puliv   
 * @Description: 选择排序,首先选出数组中最大或者最小元素,放到列表第一个元素里面      
 * @return: void      
 * @throws 
 */
@Test
public void testSelect() {
	// TODO Auto-generated method stub

	int[] nums = {3,2,5,4,6,7,8,0,1,9};
	compare(nums);
	for (int i = 0; i &lt; nums.length; i++) {
		System.out.println(nums[i]);
	}
}

@Test
public void testBullot() {

	int[] nums = {3,2,5,4,6,7,8,0,1,9};
	bullot(nums);
	for (int i = 0; i &lt; nums.length; i++) {
		System.out.println(nums[i]);
	}
}

@Test
public void testInsert() {

	int[] nums = {3,2,5,4,6,7,8,0,1,9};
	insert(nums);
	for (int i = 0; i &lt; nums.length; i++) {
		System.out.println(nums[i]);
	}
}


private  void compare(int[] nums) {
	
	int length = nums.length;
	for (int i = 0 ; i &lt; length ; i++) {
		for (int j = i+1 ; j &lt; length ; j++) {
			if (nums[i]&gt; nums[j]) {
				int tmp = nums[j];
				nums[j]=nums[i];
				nums[i] = tmp;
			}
		}	
	}
}


private  void bullot(int[] nums) {
	
	int length = nums.length;
	for (int i = 0 ; i &lt; length ; i++) {
		for (int j = 0 ; j &lt; length-i-1 ; j++) {
			if (nums[j]&gt; nums[j+1]) {
				int tmp = nums[j+1];
				nums[j+1]=nums[j];
				nums[j] = tmp;
			}
		}	
	}
}



private  void insert(int[] nums) {
	for (int i = 1; i &lt; nums.length; i++) {
		int current = nums[i];
		int preIndex = i-1;
		while(preIndex &gt;=0 &amp;&amp; nums[preIndex] &gt; current) {
			nums[preIndex+1] = nums[preIndex];//如果新加的元素小于之前的元素,那么之前的有序队列都往后挪一位
			preIndex--;
		}
		nums[preIndex+1]=current; //都挪完之后,把当前值赋值给最小的那个index
	}
}

}

 

本文由【Jacdong】发布于开源中国,原文链接:https://my.oschina.net/jacdong/blog/3158218

全部评论: 0

    我有话说: