java排序

纯粹个人的笔记，看到hadoop中的quickSort和headSort，发现原来的好东西都付之东流了，在此记一下下

 

------------------------------------

前几种，冒泡，标记都不适合实际使用，或是只用在部分排序上

堆排序实质是将树变为符合规则的大/小顶树，循环从下向上，递归从顶到下进行交换；建堆和排序两个过程都是在进行此操作

冒泡  

  一种实现可以：for 向后 for 内部向前

  for(out = nElens-1;out>0;out--)

     for(int i=0;i<out;i++)

          if(a[i]>a[out])swap();

 

--------------------------------------

选择   冒泡的变形，使用标志，而不是替换，在内部结束时进行替换

  一种实现可以：for 向前 for 内部向前

   for(out=0;n<nElens-1;out++)

      min = out;

      for(int i=0;i<n;i++)

          if(a[min]>a[i])min = i;

      swap()

 

--------------------------------------

插入   跟前边有序列比较，找到合适的位置，进行错位

for(int out = 1; n< nElens; out++)

   item = a[out];

   int in = out;

   while(in > 0 && a[in] > item)

        a[out] = a[out-1];in--;

   a[in] = item;

 

--------------------------------------

希尔 插入排序的改变，先进行分组，组内进行插入排序，知道分组数为1为止

 

        int j;  

        for(int gap = data.length / 2; gap > 0; gap /= 2){  

            for(int i = gap; i < data.length; i++){  

                Comparable temp = data[i];  

                for(j = i; j >= gap && temp.compareTo(data[j - gap]) < 0; j -= gap){  

                    data[j] = data[j - gap];  

                }  

 

                data[j] = temp;  

            }  

        }  

 

--------------------------------------

转： http://blog.csdn.net/forrestgtju/article/details/7848829

快速   分区，递归在分区，每次分区确定一个基数位置，并将队列分两半

         分区算法的一种实现：设left为基数位置，想跟right比较，再跟left比较，当left>=right，结束，并将基数放在left上int AdjustArray(int s[], int l, int r) //返回调整后基准数的位置  

{  
    int i = l, j = r;  
    int x = s[l]; //s[l]即s[i]就是第一个坑  
    while (i < j)  
    {  
        // 从右向左找小于x的数来填s[i]  
        while(i < j && s[j] >= x)   
            j--;    
        if(i < j)   
        {  
            s[i] = s[j]; //将s[j]填到s[i]中，s[j]就形成了一个新的坑  
            i++;  
        }  
  
        // 从左向右找大于或等于x的数来填s[j]  
        while(i < j && s[i] < x)  
            i++;    
        if(i < j)   
        {  
            s[j] = s[i]; //将s[i]填到s[j]中，s[i]就形成了一个新的坑  
            j--;  
        }  
    }  
    //退出时，i等于j。将x填到这个坑中。  
    s[i] = x;  
  
    return i;  
} 

另一种实现快速排序，其实理论上都一样：

             int left = i; 

        int right =j; 
        int temp = 0; 
        boolean r_or_l = true; 
        if(left>=right){ 
            return; 
        } 
        while(left<right){ 
            if(nums[left]>nums[right]){ 
                temp = nums[left]; 
                nums[left] = nums[right]; 
                nums[right] = temp; 
                r_or_l = r_or_l?false:true; 
            } 
            if(r_or_l){ 
                right--; 
            } else { 
                left++; 
            } 
        }     
        left-=1; 
        right+=1; 
        System.out.println(right+" "+left); 

        quickSort(nums, 0, left); 
        quickSort(nums, right, j); 

最后在贴一版hadoop中实现的quickSort（他好像还想用堆排序，最后给give up了，不太清楚是没写完，还是写坏了） 

 

private static void sortInternal(final IndexedSortable s, int p, int r,
      final Progressable rep, int depth) {
    if (null != rep) {
      rep.progress();
    }
    while (true) {
    if (r-p < 13) {
      for (int i = p; i < r; ++i) {
        for (int j = i; j > p && s.compare(j-1, j) > 0; --j) {
          s.swap(j, j-1);
        }
      }
      return;
    }
    if (--depth < 0) {
      // give up
      alt.sort(s, p, r, rep);
      return;
    }

    // select, move pivot into first position
    fix(s, (p+r) >>> 1, p);
    fix(s, (p+r) >>> 1, r - 1);
    fix(s, p, r-1);

    // Divide
    int i = p;
    int j = r;
    int ll = p;
    int rr = r;
    int cr;
    while(true) {
      while (++i < j) {
        if ((cr = s.compare(i, p)) > 0) break;
        if (0 == cr && ++ll != i) {
          s.swap(ll, i);
        }
      }
      while (--j > i) {
        if ((cr = s.compare(p, j)) > 0) break;
        if (0 == cr && --rr != j) {
          s.swap(rr, j);
        }
      }
      if (i < j) s.swap(i, j);
      else break;
    }
    j = i;
    // swap pivot- and all eq values- into position
    while (ll >= p) {
      s.swap(ll--, --i);
    }
    while (rr < r) {
      s.swap(rr++, j++);
    }

    // Conquer
    // Recurse on smaller interval first to keep stack shallow
    assert i != j;
    if (i - p < r - j) {
      sortInternal(s, p, i, rep, depth);
      p = j;
    } else {
      sortInternal(s, j, r, rep, depth);
      r = i;
    }
    }
  }

 

--------------------------------------

堆排序

堆排序 获得最大或最小元素,即为根元素；移除根元素，将最底元素移动至根位置。

重组树（移动新节点，最大根数要与最大子节点交换位置，反之亦然），然后递归

 

void HeapSort(SeqIAst R)
   { //对R[1..n]进行堆排序，不妨用R[0]做暂存单元
    int i；
    BuildHeap(R)； //将R[1-n]建成初始堆
    for(i=n;i>1；i--){ //对当前无序区R[1..i]进行堆排序，共做n-1趟。
      R[0]=R[1]；R[1]=R[i];R[i]=R[0]； //将堆顶和堆中最后一个记录交换
　    Heapify(R，1，i-1)； //将R[1..i-1]重新调整为堆，仅有R[1]可能违反堆性质
     } //endfor
   } //HeapSort

 

--------------------------------------

基数排序 （出自java算法和数据结构）

基数排序 是把关键字拆分 然后进行排序。一般从各位开始，按照各位分10组，从0到9。以此遍历各个位，并且以后的分组内部顺序要满足上边的顺序。输出结果可显示为：

421 240 035 532 305 430 124

（240 430） （421） （532） （124） （035 305）

（305） （421 124） （430 532 035） （240）

（035） （124） （240） （305） （421 430） （532）

 

 

---------------------------------------------------------

 

加个折半查找，呵呵

int i = (low+high)/2

if(item=a[i]) re i;

if(item>a[i])

 re find(a,i,high)

else

 re find(a,low,i)

------------------

while(low<high)

    int i = (low+high)/2

    if(item = a[i])

        break;

    if(item>a[i]) 

         low = i;

    else

         high = 1;