JAVA自学教程之（排序+二分查找+查表法）



JAVA学习第五课（排序+二分查找+查表法）.

PS:算法是不分语言的

 

排序：

1.抽取

2.交换位置

 

 

  1. import javax.swing.text.DefaultEditorKit.InsertBreakAction;
  3. import org.omg.CosNaming.NamingContextExtPackage.AddressHelper;
  6. public class Main
  7. {
  8.     public static void main(String[] args)
  9.     {
  10.     //  int[] b = new int[]{1,2,3,4,5};同下
  12. int b[] = {1,2,1,3,4,7,8,9,4,1,2,5,6,7,4,5,1,2,3,6};//同上
  14.         bubblesort(b);
  15.         System.out.println(“冒泡排序结果如下:”);
  16.         print(b);
  18.         int c[] = {1,2,1,3,4,7,8,9,4,1,2,5,6,7,4,5,1,2,3,6};
  19.         seletsort(c);
  20.         System.out.println(“选择排序结果如下:”);
  21.         print(c);
  23.         int d[] = {1,2,1,3,4,7,8,9,4,1,2,5,6,7,4,5,1,2,3,6};
  24.         Insersort(d);
  25.         System.out.println(“\n插入排序结果如下:”);
  26.         print(d);
  27.     }
  28.     static void Insersort(int b[])
  29.     {
  30.         int len = b.length;
  31.         for(int i = 1;i<len;i++)
  32.         {
  33.             if(b[i]<b[i-1])
  34.             {
  35.                 int t = b[i],j;
  36.                 b[i] = b[i-1];
  37.                 for(j = i-2;j>=0 && b[j] > t;j–)
  38.                 {
  39.                     b[j+1] = b[j];
  40.                 }
  41.                 b[j+1] = t;
  42.             }
  43.         }
  44.     }
  45.     static void swap(int x,int y,int[] b)
  46.     {
  47.         int t = b[x];
  48.         b[x] = b[y];
  49.         b[y] = t;
  50.     }
  51.     /*static void swap(int a,int b)不要写成这种方式，只是单纯的交换了两个数，
  52.      *                              但是b数组里这两个数并没有交换
  53.     {
  54.         int t = a;a = b;b = t;
  55.     }*/
  56.     static void bubblesort(int[] b)
  57.     {
  58.         int len = b.length;
  59.         for(int i = 0;i<len;i++)
  60.         {
  61.             for(int j = 0;j<len-i-1;j++)
  62.             {
  63.                 if(b[j]>b[j+1])
  64.                 {
  65.                     swap(j, j+1,b);
  66.                 }
  67.             }
  68.         }
  70.     }
  71.     static void seletsort(int a[])
  72.     {
  73.         int len = a.length;
  74.         for(int i = 0;i<len-1;i++)
  75.         {
  76.             for(int j = i+1;j<len;j++)
  77.             {
  78.                 if(a[i] > a[j])
  79.                 {
  80.                     swap(i, i+1,a);
  81.                 }
  82.             }
  83.         }
  84.     }
  85.     static void print(int b[])
  86.     {
  87.         for(int i = 0;i<b.length;i++)
  88.             System.out.println(“b["+i+"] = “+b[i]);
  89.     }
  90. }
import javax.swing.text.DefaultEditorKit.InsertBreakAction;

import org.omg.CosNaming.NamingContextExtPackage.AddressHelper;

public class Main 
{
	public static void main(String[] args)
	{
	//	int[] b = new int[]{1,2,3,4,5};同下

		int b[] = {1,2,1,3,4,7,8,9,4,1,2,5,6,7,4,5,1,2,3,6};//同上

		bubblesort(b);
		System.out.println("冒泡排序结果如下:");
		print(b);

		int c[] = {1,2,1,3,4,7,8,9,4,1,2,5,6,7,4,5,1,2,3,6};
		seletsort(c);
		System.out.println("选择排序结果如下:");
		print(c);

		int d[] = {1,2,1,3,4,7,8,9,4,1,2,5,6,7,4,5,1,2,3,6};
		Insersort(d);
		System.out.println("\n插入排序结果如下:");
		print(d);
	}
	static void Insersort(int b[])
	{
		int len = b.length;
		for(int i = 1;i<len;i++)
		{
			if(b[i]<b[i-1])
			{
				int t = b[i],j;
				b[i] = b[i-1];
				for(j = i-2;j>=0 && b[j] > t;j--)
				{
					b[j+1] = b[j];
				}
				b[j+1] = t;
			}
		}
	}
	static void swap(int x,int y,int[] b)
	{
		int t = b[x];
		b[x] = b[y];
		b[y] = t;
	}
	/*static void swap(int a,int b)不要写成这种方式，只是单纯的交换了两个数，
	 *                              但是b数组里这两个数并没有交换
	{
		int t = a;a = b;b = t;
	}*/
	static void bubblesort(int[] b)
	{
		int len = b.length;
		for(int i = 0;i<len;i++)
		{
			for(int j = 0;j<len-i-1;j++)
			{
				if(b[j]>b[j+1])
				{
					swap(j, j+1,b);
				}
			}
		}

	}
	static void seletsort(int a[])
	{
		int len = a.length;
		for(int i = 0;i<len-1;i++)
		{
			for(int j = i+1;j<len;j++)
			{
				if(a[i] > a[j])
				{
					swap(i, i+1,a);
				}
			}
		}
	}
	static void print(int b[])
	{
		for(int i = 0;i<b.length;i++)
			System.out.println("b["+i+"] = "+b[i]);
	}
}
  1. import javax.swing.text.DefaultEditorKit.InsertBreakAction;
  3. import org.omg.CosNaming.NamingContextExtPackage.AddressHelper;
  6. public class Main
  7. {
  8.     public static void main(String[] args)
  9.     {
  10.     //  int[] b = new int[]{1,2,3,4,5};同下
  12.         Scanner cin = new Scanner(System.in);
  14.         int b[] = new int[11];
  15.         for(int i = 0;i<11;i++)
  16.         {
  17.             b[i] = cin.nextInt();
  18.         }
  19.         bubblesort(b);
  20.         System.out.println(“冒泡排序结果如下:”);
  21.         print(b);
  22.         System.out.print(“请输入你要查找的值：”);
  23.         int n;
  24.         n = cin.nextInt();
  26.         boolean flag = B_search(n,b);
  28.         if(flag==true)
  29.             System.out.println(“YES”);
  30.         else
  31.             System.out.println(“NO”);
  33.         cin.close();
  34.     }
  36.     static void swap(int x,int y,int[] b)
  37.     {
  38.         int t = b[x];
  39.         b[x] = b[y];
  40.         b[y] = t;
  41.     }
  42.     static boolean B_search(int n,int b[])
  43.     {
  44.         int low = 0,high = b.length-1;
  46.         while(low<=high)
  47.         {
  48.             int mid = ( low + high ) / 2;
  49.             if(b[mid] == n)
  50.             {
  51.                 return true;
  52.             }
  53.             else if(b[mid] > n)
  54.             {
  55.                 high = mid – 1;
  56.             }
  57.             else
  58.             {
  59.                 low = mid + 1;
  60.             }
  61.         }
  62.         return false;
  63.     }
  64.     static void bubblesort(int[] b)
  65.     {
  66.         int len = b.length;
  67.         for(int i = 0;i<len;i++)
  68.         {
  69.             for(int j = 0;j<len-i-1;j++)
  70.             {
  71.                 if(b[j]>b[j+1])
  72.                 {
  73.                     swap(j, j+1,b);
  74.                 }
  75.             }
  76.         }
  78.     }
  79.     static void print(int b[])
  80.     {
  81.         for(int i = 0;i<b.length;i++)
  82.             System.out.println(“b["+i+"] = “+b[i]);
  83.     }
  84. }


import javax.swing.text.DefaultEditorKit.InsertBreakAction;

import org.omg.CosNaming.NamingContextExtPackage.AddressHelper;

public class Main 
{
	public static void main(String[] args)
	{
	//	int[] b = new int[]{1,2,3,4,5};同下

		Scanner cin = new Scanner(System.in);

		int b[] = new int[11];
		for(int i = 0;i<11;i++)
		{
			b[i] = cin.nextInt();
		}
		bubblesort(b);
		System.out.println("冒泡排序结果如下:");
		print(b);
		System.out.print("请输入你要查找的值：");
		int n;
		n = cin.nextInt();

		boolean flag = B_search(n,b);

		if(flag==true)
			System.out.println("YES");
		else
			System.out.println("NO");

		cin.close();
	}

	static void swap(int x,int y,int[] b)
	{
		int t = b[x];
		b[x] = b[y];
		b[y] = t;
	}
	static boolean B_search(int n,int b[])
	{
		int low = 0,high = b.length-1;

		while(low<=high)
		{
			int mid = ( low + high ) / 2;
			if(b[mid] == n)
			{
				return true;
			}
			else if(b[mid] > n)
			{
				high = mid - 1;
			}
			else
			{
				low = mid + 1;
			}
		}
		return false;
	}
	static void bubblesort(int[] b)
	{
		int len = b.length;
		for(int i = 0;i<len;i++)
		{
			for(int j = 0;j<len-i-1;j++)
			{
				if(b[j]>b[j+1])
				{
					swap(j, j+1,b);
				}
			}
		}

	}
	static void print(int b[])
	{
		for(int i = 0;i<b.length;i++)
			System.out.println("b["+i+"] = "+b[i]);
	}
}

 

 

二分查找：面试题 给个一个有序数组，如果往这个数组中存储一个元素，并保证这个数组还是有序的，那么这个元素的存储的角标如何获取

  1. import java.util.Arrays;
  2. import java.util.Scanner;
  5. import javax.swing.text.DefaultEditorKit.InsertBreakAction;
  8. import org.omg.CosNaming.NamingContextExtPackage.AddressHelper;
  13. public class Main
  14. {
  15.     public static void main(String[] args)
  16.     {
  17.     //  int[] b = new int[]{1,2,3,4,5};同下
  19.         Scanner cin = new Scanner(System.in);
  21.         int b[] = new int[11];
  22.         for(int i = 0;i<11;i++)
  23.         {
  24.             b[i] = cin.nextInt();
  25.         }
  26.         bubblesort(b);
  27.         System.out.println(“冒泡排序结果如下:”);
  28.         print(b);
  29.         System.out.print(“请输入你要查找的值：”);
  30.         int n;
  31.         n = cin.nextInt();
  32.         System.out.println(“手写二分查找:”);
  33.         int flag = B_search(n,b);
  35.         System.out.println(“下标为：\t”+flag);
  36.             int wz = cin.nextInt();
  37.         int indx = Arrays.binarySearch(b, wz);//返回的是个：负的插入点下标再减1
  38.         //返回负数，代表着不存在，如果我往里放这个元素，插入点在哪，负数指的是：负的插入点下标，再-1
  39.         //返回正数，代表着其下标
  40.         /*为什么要减1？
  41.          * 如果要插入的元素比数组元素的第一个还小，不减1，会返回0，而返回0，是不是就这个数代表着不存在，故要减1
  42.          * */
  43.         System.out.println(“调用二分查找:”);
  44.         System.out.println(“下标为：\t”+indx);
  45.         cin.close();
  46.     }
  48.     static void swap(int x,int y,int[] b)
  49.     {
  50.         int t = b[x];
  51.         b[x] = b[y];
  52.         b[y] = t;
  53.     }
  54.     static int B_search(int n,int b[])
  55.     {
  56.         int low = 0,high = b.length-1;
  58.         while(low<=high)
  59.         {
  60.             int mid = ( low + high ) / 2;
  61.             if(b[mid] == n)
  62.             {
  63.                 return mid;
  64.             }
  65.             else if(b[mid] > n)
  66.             {
  67.                 high = mid – 1;
  68.             }
  69.             else
  70.             {
  71.                 low = mid + 1;
  72.             }
  73.         }
  74.         return low;
  75.     }
  76.     static void bubblesort(int[] b)
  77.     {
  78.         int len = b.length;
  79.         for(int i = 0;i<len;i++)
  80.         {
  81.             for(int j = 0;j<len-i-1;j++)
  82.             {
  83.                 if(b[j]>b[j+1])
  84.                 {
  85.                     swap(j, j+1,b);
  86.                 }
  87.             }
  88.         }
  90.     }
  91.     static void print(int b[])
  92.     {
  93.         for(int i = 0;i<b.length;i++)
  94.             System.out.println(“b["+i+"] = “+b[i]);
  95.     }
  96. }
import java.util.Arrays;
import java.util.Scanner;

import javax.swing.text.DefaultEditorKit.InsertBreakAction;

import org.omg.CosNaming.NamingContextExtPackage.AddressHelper;

public class Main 
{
	public static void main(String[] args)
	{
	//	int[] b = new int[]{1,2,3,4,5};同下

		Scanner cin = new Scanner(System.in);

		int b[] = new int[11];
		for(int i = 0;i<11;i++)
		{
			b[i] = cin.nextInt();
		}
		bubblesort(b);
		System.out.println("冒泡排序结果如下:");
		print(b);
		System.out.print("请输入你要查找的值：");
		int n;
		n = cin.nextInt();
		System.out.println("手写二分查找:");
		int flag = B_search(n,b);

		System.out.println("下标为：\t"+flag);
			int wz = cin.nextInt();
		int indx = Arrays.binarySearch(b, wz);//返回的是个：负的插入点下标再减1
		//返回负数，代表着不存在，如果我往里放这个元素，插入点在哪，负数指的是：负的插入点下标，再-1
		//返回正数，代表着其下标
		/*为什么要减1？
		 * 如果要插入的元素比数组元素的第一个还小，不减1，会返回0，而返回0，是不是就这个数代表着不存在，故要减1
		 * */
		System.out.println("调用二分查找:");
		System.out.println("下标为：\t"+indx);
		cin.close();
	}

	static void swap(int x,int y,int[] b)
	{
		int t = b[x];
		b[x] = b[y];
		b[y] = t;
	}
	static int B_search(int n,int b[])
	{
		int low = 0,high = b.length-1;

		while(low<=high)
		{
			int mid = ( low + high ) / 2;
			if(b[mid] == n)
			{
				return mid;
			}
			else if(b[mid] > n)
			{
				high = mid - 1;
			}
			else
			{
				low = mid + 1;
			}
		}
		return low;
	}
	static void bubblesort(int[] b)
	{
		int len = b.length;
		for(int i = 0;i<len;i++)
		{
			for(int j = 0;j<len-i-1;j++)
			{
				if(b[j]>b[j+1])
				{
					swap(j, j+1,b);
				}
			}
		}

	}
	static void print(int b[])
	{
		for(int i = 0;i<b.length;i++)
			System.out.println("b["+i+"] = "+b[i]);
	}
}

 

查表法

 

 

  1. import java.util.Scanner;
  4. public class Main
  5. {
  6.     /*
  7.      * 使用查表法
  9.      */
  11.     /*查表法的应用：
  12.      * 有规律的，就可以使用查表法
  13.      * */
  14.     public static void main(String[] args)
  15.     {
  16.         Scanner cin = new Scanner(System.in);
  18.         {
  19.             int x = cin.nextInt();
  20.             /*
  21.              * 查询星期
  22.              * */
  23.             System.out.println(Find(x));
  25.             /*
  26.              * 查询月份
  27.              * */
  28.             int y = cin.nextInt();
  29.             System.out.println(Findd(y));
  30.             cin.close();
  32.         }
  34.     }
  35.     public  static String Find(int x)
  36.     {
  37.         if(x>7 || x<0)
  38.         {
  39.             return “输入错误”;
  40.         }
  41.         String[] week = {“星期一 = Monday”,”星期二 = Tuesday”,”星期三 = Wednesday”,”星期四 = Thurseday”,”星期五 = Friday”,”星期六 = Saturday”,”星期天 = Sunday”};
  42.         return week[x-1];
  43.     }
  44.     public  static String Findd(int x)
  45.     {
  46.         if(x>12 || x<0)
  47.         {
  48.             return “输入错误”;
  49.         }
  50.         String[] mon = {“一月 = January”,”二月  = Febary”,”三月 = March”,”四月 = April”,”五月 = May”
  51.                 ,”六月 = June”,”七月 = July”,”八月 = August”,”九月   = Spetember”,”十月  = October”,”十一月  = November”,”十二月  = December”};
  52.         return mon[x-1];
  53.     }
  55. }