剪切排序

选一种语言就能看到代码

def shear_sort(grid, w, h):
    rounds = math.ceil(math.log2(h)) + 1
    for _ in range(rounds):
        sort_rows(grid, w, h)
        sort_columns(grid, w, h)
    sort_rows(grid, w, h)


def sort_rows(grid, w, h):
    for y in range(h):
        row = sorted(grid[y * w:(y + 1) * w], reverse=y % 2 == 1)
        grid[y * w:(y + 1) * w] = row


def sort_columns(grid, w, h):
    for x in range(w):
        column = sorted(grid[x + y * w] for y in range(h))
        for y in range(h):
            grid[x + y * w] = column[y]

function shearSort(grid, w, h) {
  const rounds = Math.ceil(Math.log2(h)) + 1;
  for (let r = 0; r < rounds; r++) {
    sortRows(grid, w, h);
    sortColumns(grid, w, h);
  }
  sortRows(grid, w, h);
}

function sortRows(grid, w, h) {
  for (let y = 0; y < h; y++) {
    const row = grid.slice(y * w, y * w + w).sort((p, q) => p - q);
    if (y % 2 === 1) row.reverse();
    for (let x = 0; x < w; x++) grid[y * w + x] = row[x];
  }
}

function sortColumns(grid, w, h) {
  for (let x = 0; x < w; x++) {
    const column = [];
    for (let y = 0; y < h; y++) column.push(grid[y * w + x]);
    column.sort((p, q) => p - q);
    for (let y = 0; y < h; y++) grid[y * w + x] = column[y];
  }
}

static void sort_rows(int grid[], int w, int h) {
    for (int y = 0; y < h; y++) {
        insertion_sort(grid + y * w, w);
        if (y % 2 == 1) reverse(grid + y * w, w);
    }
}

static void sort_columns(int grid[], int w, int h) {
    int* column = malloc(sizeof(int) * h);
    for (int x = 0; x < w; x++) {
        for (int y = 0; y < h; y++) column[y] = grid[y * w + x];
        insertion_sort(column, h);
        for (int y = 0; y < h; y++) grid[y * w + x] = column[y];
    }
    free(column);
}

void shear_sort(int grid[], int w, int h) {
    int rounds = 1;
    while ((1 << rounds) < h) rounds++;
    for (int r = 0; r <= rounds; r++) {
        sort_rows(grid, w, h);
        sort_columns(grid, w, h);
    }
    sort_rows(grid, w, h);
}

static void sort_rows(std::vector<int>& grid, int w, int h) {
    for (int y = 0; y < h; y++) {
        auto begin = grid.begin() + y * w;
        std::sort(begin, begin + w);
        if (y % 2 == 1) std::reverse(begin, begin + w);
    }
}

static void sort_columns(std::vector<int>& grid, int w, int h) {
    std::vector<int> column(h);
    for (int x = 0; x < w; x++) {
        for (int y = 0; y < h; y++) column[y] = grid[y * w + x];
        std::sort(column.begin(), column.end());
        for (int y = 0; y < h; y++) grid[y * w + x] = column[y];
    }
}

void shear_sort(std::vector<int>& grid, int w, int h) {
    int rounds = static_cast<int>(std::ceil(std::log2(h))) + 1;
    for (int r = 0; r < rounds; r++) {
        sort_rows(grid, w, h);
        sort_columns(grid, w, h);
    }
    sort_rows(grid, w, h);
}

static void SortRows(int[] grid, int w, int h) {
    for (int y = 0; y < h; y++) {
        Array.Sort(grid, y * w, w);
        if (y % 2 == 1) Array.Reverse(grid, y * w, w);
    }
}

static void SortColumns(int[] grid, int w, int h) {
    int[] column = new int[h];
    for (int x = 0; x < w; x++) {
        for (int y = 0; y < h; y++) column[y] = grid[y * w + x];
        Array.Sort(column);
        for (int y = 0; y < h; y++) grid[y * w + x] = column[y];
    }
}

static void ShearSort(int[] grid, int w, int h) {
    int rounds = (int)Math.Ceiling(Math.Log2(h)) + 1;
    for (int r = 0; r < rounds; r++) {
        SortRows(grid, w, h);
        SortColumns(grid, w, h);
    }
    SortRows(grid, w, h);
}

static void sortRows(int[] grid, int w, int h) {
    for (int y = 0; y < h; y++) {
        Arrays.sort(grid, y * w, y * w + w);
        if (y % 2 == 1) reverse(grid, y * w, w);
    }
}

static void sortColumns(int[] grid, int w, int h) {
    int[] column = new int[h];
    for (int x = 0; x < w; x++) {
        for (int y = 0; y < h; y++) column[y] = grid[y * w + x];
        Arrays.sort(column);
        for (int y = 0; y < h; y++) grid[y * w + x] = column[y];
    }
}

static void shearSort(int[] grid, int w, int h) {
    int rounds = (int) Math.ceil(Math.log(h) / Math.log(2)) + 1;
    for (int r = 0; r < rounds; r++) {
        sortRows(grid, w, h);
        sortColumns(grid, w, h);
    }
    sortRows(grid, w, h);
}