算法分析复习笔记-排序

算法分析课程复习笔记 - 排序

冒泡排序

C++实现

#include<iostream>

using namespace std;

int main(){
  int data[8] = {50,13,55,97,27,38,49,65};
  int exchange = 1;
  while(exchange){
    exchange = 0;
    for (int j = 0; j < 8 - 1; j++) {
      if( data[j] > data[j+1]){
        int temp = data[j+1];
        data[j+1] = data[j];
        data[j] = temp;
        exchange = 1;
      }
    }
    for (int i = 0; i < 8; i++) {
      cout<<data[i]<<" ";
    }
    cout<<endl;
  }
  for (int i = 0; i < 8; i++) {
    cout<<data[i]<<" ";
  }
  cout<<endl;
  return 0;
}

二路归并排序 JAVA

import java.util.Arrays;

public class MergeSort {
    
    public static void main(String[] args) {
        int[] array = {9,10,21,3,6,22,21,33};
        mergeSort(array,0,array.length - 1,new int[array.length]);
        System.out.println(Arrays.toString(array));
    }
    
    public static void mergeSort(int[] array , int left , int right,int[] temp) {
        if( left < right ) {
            int center = (left + right) / 2;
            mergeSort(array,left,center,temp);
            mergeSort(array,center+1,right,temp);
            merge(array,left,center,right,temp);
        }
    }
    
    public static void merge(int[] array , int left , int center ,  int right, int[] temp) {
        int currentLeft = left;
        int currentRight = center + 1;
        int tempArrayPos = currentLeft;
        while(currentLeft <= center && currentRight <= right) {
            if(array[currentLeft] <= array[currentRight]) {
                temp[tempArrayPos ++ ] = array[currentLeft++];
            }else {
                temp[tempArrayPos++ ] = array[currentRight++];
            }
        }
        
        while( currentLeft <= center ) {
            temp[tempArrayPos ++ ] = array[currentLeft++];
        }
        
        while(currentRight <= right) {
            temp[tempArrayPos++ ] = array[currentRight++];
        }
        
        for(int i = left ; i <= right ; i ++  ) {
            array[i] = temp[i];
        }
        
    }

}

快速排序

void qsort(int begin,int end,int nums[]){
  if(begin < end){
    int left = begin;
    int right = end;
    int flag = nums[begin];
    while(left<right){
      while(left < right && nums[right] >= flag){
        right --;
      }
      if(left<right){
        nums[left++] = nums[right];
      }
      while(left<right && nums[left] < flag){
        left ++;
      }
      if(left<right){
        nums[right--] = nums[left];
      }
    }
    nums[left]=flag;
    qsort(begin,left-1,nums);
    qsort(left+1,end,nums);
  }
}
标签: none
返回文章列表 文章二维码
本页链接的二维码
打赏二维码