posts - 195, comments - 34, trackbacks - 0, articles - 1

          Sorting

          Posted on 2009-10-26 11:53 小強摩羯座 閱讀(181) 評論(0)  編輯  收藏 所屬分類: 算法編程

           

            1package dwq.algo.sort;
            2
            3import java.util.Arrays;
            4
            5public class Sorting
            6{
            7
            8    public static void main(String[] args)
            9    {
           10        // int []a = {2,1, 3, 5, 4};
           11        //        
           12        // bubbleSort(a);
           13        // System.out.println( Arrays.toString(a));
           14        // //Integer []b = {7,1, 3, 5, 4};
           15        // //
           16        Integer[] b = 11847 };
           17        insertSort(b, b.length);
           18
           19        System.out.println(Arrays.toString(b));
           20
           21        int[] c = 213254233456 ,-10110};// 12
           22        heapSort(c);
           23
           24        System.out.println("heap sort " + Arrays.toString(c));
           25
           26        int[] re = const2ElemSum(c, 3);
           27        if (re.length == 2)
           28            System.out.println(Arrays.toString(re));
           29
           30        int[] a = 12385917 };
           31        int re2 = const2ElemSum2(a, 8);
           32        System.out.println(re2);
           33    }

           34
           35    /**
           36     * 
           37     * @param a
           38     * @param x
           39     * @return :int[2]:i,j when a[i] + a[j] == x
           40     */

           41    static int[] const2ElemSum(int[] a, int x)
           42    {
           43        quickSort(a);
           44        int sum = 0;
           45        for (int i = 0, j = a.length - 1; i < j;)
           46        {
           47            sum = a[i] + a[j];
           48            if (sum == x) return new int[] { a[i], a[j] };
           49            else if (x > sum) i++;
           50            else j--;
           51        }

           52        return new int[] {};
           53    }

           54
           55    /**
           56     * 題目條件:a是一個集合的元素,則各數(shù)不同。則可正確統(tǒng)計出存在兩數(shù)為和的對數(shù) 利用了原理:若a, x-a存在于集合中則條件滿
           57
           58足。所以
           59     * 
           60     * @param a
           61     * @param x
           62     * @return
           63     */

           64    static int const2ElemSum2(int[] a, int x)
           65    {
           66        // int []b = new int[a.length];
           67        int[] c = new int[2 * a.length];
           68        for (int i = 0; i < a.length; i++)
           69        {
           70            c[i] = a[i];
           71            // b[i] = x - a[i];
           72            c[a.length + i] = x - a[i];
           73        }

           74        quickSort(c);
           75        int count = 0;
           76        for (int i = 1, tmp = c[0]; i < c.length; i++)
           77        {
           78            if (tmp == c[i])
           79            {
           80                count++;
           81                if (i < c.length - 1)
           82                    tmp = c[++i];// tmp設(shè)置為i的下一個
           83            }
           else tmp = c[i];
           84        }

           85        return count / 2;
           86    }

           87
           88    /**
           89     * 嚴蔚敏書上的冒泡排序算法,有利用交換與否進行改進
           90     * 
           91     * @param a
           92     */

           93    static void bubbleSort(int[] a)
           94    {
           95        boolean change = true;
           96        for (int i = a.length - 1; i > 0 && change; i--)// i > 0即可因為i =
           97        // 1時有二個元素比較過了。一個無需比較
           98        {
           99            for (int j = 0; j < i; j++)
          100            {
          101                change = false;
          102                if (a[j] > a[j + 1])
          103                {
          104                    change = true;
          105                    a[j] = a[j] + a[j + 1- (a[j + 1= a[j]);
          106                }

          107            }

          108        }

          109    }

          110
          111    static void quickSort(int[] a)
          112    {
          113        System.out.println(" call my QS");
          114        quickSort(a, 0, a.length - 1);
          115    }

          116
          117    static void quickSort(int[] a, int left, int right)
          118    {
          119        if (left < right) // 這里是if, 給寫成了while
          120        {
          121            // int j = partition(a, left, right);
          122            int pivot = a[left];
          123            int i = left;
          124            int j = right + 1;
          125            while (true)// 一定是true, 使用break退出的
          126            {
          127                while (i < right && a[++i] <= pivot)
          128                    ;
          129                while (j > left && a[--j] >= pivot)
          130                    ; // a[left] end it.
          131                // 錯誤代碼:每次i都必然會++的,但是這顯然不對
          132                // while( a[++i] <= pivot | a[--j] >= pivot) if(j <= i) break;
          133                if (j <= i) break// 這里也必須有相等,否則對2,1排不了,因為其實本身這時交換就沒有意義了,=出
          134
          135現(xiàn)在一個到頭時
          136                a[j] = a[j] + a[i] - (a[i] = a[j]);
          137            }

          138            a[j] = a[j] + a[left] - (a[left] = a[j]);
          139            quickSort(a, left, j - 1);
          140            quickSort(a, j + 1, right);
          141        }

          142    }

          143
          144    /**
          145     * 1、最后pivot位置確定:pivot 取在第一個,為從后到前指針交流,取最后一個話,與從前到后指針交換 2、對等號的有無,
          146     * 應(yīng)該有,這樣可以跳過與pivot相等,移動快一次
          147     * 
          148     * @param a
          149     * @param left
          150     * @param right
          151     * @return
          152     */

          153    static int partition(int a[], int left, int right)
          154    {
          155        int pivot = a[left];
          156        int i = left;
          157        int j = right + 1;
          158        while (true)// 一定是true, 使用break退出的
          159        {
          160            while (i < right && a[++i] <= pivot)
          161                ;
          162            while (j > left && a[--j] >= pivot)
          163                ; // a[left] end it.
          164            if (i >= j)
          165                break;
          166            a[j] = a[j] + a[i] - (a[i] = a[j]);
          167        }

          168        a[j] = a[j] + a[left] - (a[left] = a[j]);
          169        return j;
          170    }

          171
          172    static <extends Comparable<T>> void quickSort(T[] data)
          173    {
          174        quickSort(data, 0, data.length - 1);
          175    }

          176
          177    private static <extends Comparable<T>> void quickSort(T[] data, int left,
          178            int right)
          179    {
          180        if (left + 10 <= right)
          181        {
          182            T pivot = middle3(data, left, right);// 執(zhí)行三數(shù)中值分割法, pivot =
          183            // data[last]
          184            int i = left, j = right - 1;
          185            for (;;)
          186            {
          187                while (data[++i].compareTo(pivot) < 0)
          188                {
          189                }

          190                while (data[--j].compareTo(pivot) > 0)
          191                {
          192                }

          193                if (i < j)
          194                {
          195                    swap(data, i, j);
          196                }
           else
          197                {
          198                    break;
          199                }

          200            }

          201            swap(data, i, right - 1);
          202            quickSort(data, left, i - 1);
          203            quickSort(data, i + 1, right);
          204        }
           else
          205        {
          206            System.out.println("insertionSort() in Quicksort");
          207            insertionSort(data);
          208        }

          209    }

          210
          211    private static <extends Comparable<T>> T middle3(T[] data, int left,
          212            int right)
          213    {
          214        int center = (left + right) / 2;
          215        if (data[center].compareTo(data[left]) < 0)
          216        {
          217            swap(data, left, center);
          218        }

          219        if (data[right].compareTo(data[left]) < 0)
          220        {
          221            swap(data, left, right);
          222        }

          223        if (data[right].compareTo(data[center]) < 0)
          224        {
          225            swap(data, center, right);
          226        }

          227        swap(data, center, right - 1); // 取中元素最后放到了末尾
          228        return data[right - 1];
          229    }

          230
          231    private static <extends Comparable<T>> void swap(T[] data, int i, int j)
          232    {
          233        T temp = data[i];
          234        data[i] = data[j];
          235        data[j] = temp;
          236    }

          237
          238    // 插入排序;
          239    public static <extends Comparable<T>> void insertionSort(T[] data)
          240    {
          241        System.out.println("insertSort() ");
          242        int j;
          243        for (int p = 1; p < data.length; p++)
          244        {
          245            T temp = data[p];
          246            for (j = p; j > 0 && temp.compareTo(data[j - 1]) < 0; j--)
          247            {
          248                data[j] = data[j - 1];
          249            }

          250            data[j] = temp;
          251        }

          252    }

          253
          254    public static <extends Comparable<T>> void insertSort(T[] data, int n)
          255    {
          256        if (n == 1return;
          257        insertSort(data, n - 1);
          258        int j;
          259        for (int p = 1; p < n; p++)
          260        {
          261            T temp = data[p];
          262            for (j = p; j > 0 && temp.compareTo(data[j - 1]) < 0; j--)
          263            {
          264                data[j] = data[j - 1];
          265            }

          266            data[j] = temp;
          267        }

          268    }

          269
          270    static void heapSort(int[] a)
          271    {
          272        //builder the heap
          273        int size = a.length;
          274        for(int i = (size-1)/2; i >= 0;i--)
          275            maxHeapity(a, i, size);
          276        // for i= size - 2, exchagne to last
          277        for(int i = size -1;i > 0;i--)
          278        {
          279            a[0= a[0+ a[i] - ( a[i] = a[0]);
          280            size -= 1;
          281            maxHeapity(a, 0, size);
          282        }

          283    }

          284
          285    static void maxHeapity(int[] a, int i, int size)
          286    {
          287        int left = (i << 1+ 1// i * 2 + 1,當(dāng)下標(biāo)從0正式開始時
          288        int right = (i << 1+ 2;
          289        int t;
          290        if ( left<size && a[left]>a[i] ) t = left;
          291        else t = i;
          292        if (right < size && a[right] > a[t])
          293            t = right;
          294        if( t != i)
          295        {
          296            a[t] = a[i] + a[t] - ( a[i] = a[t]);
          297            maxHeapity(a, t, size);
          298        }

          299    }

          300}

          301


          主站蜘蛛池模板: 阿坝县| 桑植县| 广东省| 湟源县| 扶风县| 木兰县| 甘德县| 洪泽县| 延川县| 城固县| 津市市| 阳春市| 郧西县| 阳泉市| 新余市| 通榆县| 梅河口市| 五原县| 宜川县| 嘉荫县| 五峰| 汉源县| 达拉特旗| 永善县| 兴化市| 汽车| 南乐县| 库尔勒市| 东台市| 洛南县| 肥乡县| 鄂托克前旗| 竹北市| 庄河市| 塔河县| 洞头县| 土默特左旗| 广东省| 怀宁县| 九台市| 达拉特旗|