现在的位置: 首页 > 综合 > 正文

冒泡排序、选择排序、插入排序、快速排序算法的时间性能分析（java实现）

2013年10月10日 ⁄ 综合 ⁄ 共 3859字 ⁄ 字号 小 中 大 ⁄ 评论关闭

冒泡排序、选择排序、插入排序、快速排序算法的时间性能分析（java实现）

  3. public class Sort
  4. {
  6.     public void swap(int a[], int i, int j)
  7.     {
  8.         int tmp = a[i];
  9.         a[i] = a[j];
  10.         a[j] = tmp;
  11.     }
  13.     public int partition(int a[], int low, int high)
  14.     {
  15.         int pivot, p_pos, i;
  16.         p_pos = low;
  17.         pivot = a[p_pos];
  18.         for (i = low + 1; i <= high; i++)
  19.         {
  20.             if (a[i] > pivot)
  21.             {
  22.                 p_pos++;
  23.                 swap(a, p_pos, i);
  24.             }
  25.         }
  26.         swap(a, low, p_pos);
  27.         return p_pos;
  28.     }
  30.     public void quicksort(int a[], int low, int high)
  31.     {
  32.         int pivot;
  33.         if (low < high)
  34.         {
  35.             pivot = partition(a, low, high);
  36.             quicksort(a, low, pivot - 1);
  37.             quicksort(a, pivot + 1, high);
  38.         }
  40.     }
  42.     public static void main(String args[])
  43.     {
  44.         int vec[] = new int[] { 77, 19, 27, -9, 19, 34 };
  45.         int temp;
  46.         
  47.         System.out.println("对37, 47, 23, -5, 19, 56进行排序");
  48.         // 选择排序法(Selection Sort)
  49.         long begin = System.currentTimeMillis();
  50.         for (int k = 0; k < 1000000; k++)
  51.         {
  52.             for (int i = 0; i < vec.length; i++)
  53.             {
  54.                 for (int j = i; j < vec.length; j++)
  55.                 {
  56.                     if (vec[j] > vec[i])
  57.                     {
  58.                         temp = vec[i];
  59.                         vec[i] = vec[j];
  60.                         vec[j] = temp;
  61.                     }
  62.                 }
  64.             }
  65.         }
  66.         long end = System.currentTimeMillis();
  67.         System.out.println(); //另起一行
  68.         System.out.println("选择法用时为：" + (end - begin) + "/n排序结果：");
  69.         // 打印排序好的结果
  70.         for (int i = 0; i < vec.length; i++)
  71.         {
  72.             System.out.print(vec[i]);
  73.             System.out.print("  ");
  74.         }
  75.         // 冒泡排序法(Bubble Sort)
  76.         begin = System.currentTimeMillis();
  77.         for (int k = 0; k < 1000000; k++)
  78.         {
  79.             for (int i = 0; i < vec.length; i++)
  80.             {
  81.                 for (int j = i; j < vec.length - 1; j++)
  82.                 {
  83.                     if (vec[j + 1] > vec[j])
  84.                     {
  85.                         temp = vec[j + 1];
  86.                         vec[j + 1] = vec[j];
  87.                         vec[j] = temp;
  88.                     }
  89.                 }
  91.             }
  92.         }
  93.         end = System.currentTimeMillis();
  94.         System.out.println(); //另起一行
  95.         System.out.println("冒泡法用时为：" + (end - begin)+ "/n排序结果：");
  96.         // 打印排序好的结果
  97.         for (int i = 0; i < vec.length; i++)
  98.         {
  99.             System.out.print(vec[i]);
  100.             System.out.print("  ");
  101.         }
  103.         // 插入排序法(Insertion Sort)
  104.         begin = System.currentTimeMillis();
  105.         for (int k = 0; k < 1000000; k++)
  106.         {
  107.             for (int i = 1; i < vec.length; i++)
  108.             {
  109.                 int j = i;
  110.                 while (vec[j - 1] < vec[i])
  111.                 {
  112.                     vec[j] = vec[j - 1];
  113.                     j--;
  114.                     if (j <= 0)
  115.                     {
  116.                         break;
  117.                     }
  118.                 }
  119.                 vec[j] = vec[i];
  120.             }
  121.         }
  122.         end = System.currentTimeMillis();
  123.         System.out.println(); //另起一行
  124.         System.out.println("插入法用时为：" + (end - begin)+ "/n排序结果：");
  125.         // 打印排序好的结果
  126.         for (int i = 0; i < vec.length; i++)
  127.         {
  128.             System.out.print(vec[i]);
  129.             System.out.print("  ");
  130.         }
  132.         // 快速排序法(Quick Sort)
  134.         Sort s = new Sort();
  135.         begin = System.currentTimeMillis();
  136.         for (int k = 0; k < 1000000; k++)
  137.         {
  138.             s.quicksort(vec, 0, 5);
  139.         }
  140.         end = System.currentTimeMillis();
  141.         System.out.println(); //另起一行
  142.         System.out.println("快速法用时为：" + (end - begin)+ "/n排序结果：");
  143.         // 打印排序好的结果
  144.         for (int i = 0; i < vec.length; i++)
  145.         {
  146.             System.out.print(vec[i]);
  147.             System.out.print("  ");
  148.         }
  149.     }
  151. }

 

返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞